Given a linked list, swap every two adjacent nodes and return its head.
Example:
Given 1->2->3->4, you should return the list as 2->1->4->3.
Note:
Your algorithm should use only constant extra space. You may not modify the values in the list’s nodes, only nodes itself may be changed.
Corner cases:
Odd number
Empty linked list
If the linked list is empty, we will return.
sol
Use cur_node.next != None to see if the current node has pair
Use cur_node != None to see if we have reached the end
three place holder node pointer
Cur
Cur points to the current node. It is inited as
Prev
Prev points to the node before current node
Order of operations
Use prev ptr to store the previous node and point
Use of dummy head
Get rid of special treatment for head and allow us to use pre at the beginning
Code
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
dummy_head = ListNode(1)
dummy_head.next = head
cur = head
prev = dummy_head
if not cur:
return None
while cur and cur.next:
temp = cur.next
prev.next = temp
cur.next = temp.next
temp.next = cur
prev = cur
cur = cur.next
return dummy_head.next