Problem: Given a linked list, swap every two adjacent nodes and return its head.
You may not modify the values in the list’s nodes, only nodes itself may be changed.
Example:
Given 1->2->3->4, you should return the list as 2->1->4->3.
iterative solution: main idea: to use dummy node to record head and cur node to track start of local swap operation time complexity O(N) space: O(1)
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
dummy = ListNode(-1)
dummy.next = head
cur = dummy
while cur.next and cur.next.next:
first = cur.next
sec = cur.next.next
# confirm head after switch
cur.next = sec
first.next = sec.next
sec.next = first
# new dummy for the next round
cur = cur.next.next
return dummy.next
easier to remember
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
dummy = ListNode(next = head)
cur_dummy = dummy
while cur_dummy.next and cur_dummy.next.next:
n1,n2,n3 = cur_dummy.next,cur_dummy.next.next,cur_dummy.next.next.next
# confirm current head after switch
cur_dummy.next = n2
n1.next = n2.next
n2.next = n1
# confirm new dummy node
cur_dummy = n1
return dummy.next
solution 2: recursive
class Solution:
# time O(N) space O(N/2)
def swapPairs(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
new_start = head.next.next
head,head.next = head.next, head
head.next.next = self.swapPairs(new_start)
return head