• Uncategorized
  • 0

[leetcode] 24. Exchange the nodes in the linked list pairwise

Hits: 0

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.

Iterative method

  1. while cur and cur.next: be sure to check if None.next is possible
  2. 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

recursion

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

You may also like...

Leave a Reply

Your email address will not be published.