[leetcode] 24. Exchange the nodes in the linked list pairwise
a. Iterative version. Define the predecessor node, odd node, and even node of odd-numbered nodes. In each iteration, let the predecessor node point to the even-numbered node, then let the odd-numbered node point to the next even-numbered node, and finally let the even-numbered node point to the odd-numbered node. point.
b. Recursive version. Define even-numbered nodes and odd-numbered nodes, let the odd-numbered node point to the next node in the node, then let the even-numbered node point to the odd-numbered node, and return the even-numbered node.
- while cur and cur.next: be sure to check if None.next is possible
- Consider special test cases, such as the linked list is empty and the linked list has only one node, the linked list has only two nodes,
# class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def swapPairs(self, head): dummy = ListNode(- 1 ) dummy.next = head pre, cur = dummy, head while cur and cur. next: ## The exchange list needs to be saved: the previous one, node 1, node 2, the next one (will be temporarily connected to node 1 later) ## This is simplified to 3 variables, that is, the previous one , node 1, node 2 nex = cur. next ## two nodes exchange pre. next = nex cur.next = nex.next nex.next = cur ## Update pre and cur pre, cur = cur, cur.next return dummy.next
def swapPairs(self, head: ListNode) -> ListNode: # If the list has no node or has only one node left. if not head or not head.next: return head # Nodes to be swapped first, second = head, head.next # Swapping first.next = self.swapPairs(second.next) second.next = first # Now the head is the second node return second