Given a linked list, swap adjacent nodes in pairs and return the swapped list. You can’t just change the values inside a node, you need to actually swap nodes.

Enter: head = [1.2.3.4] output: [2.1.4.3]
Copy the code

Method a

Iterate on what you did before looking at the answer. The main idea is to take two nodes, node1 and node2, and swap them so that the next node of Node1 points to the child node of Node2, and finally join the whole node behind the target list.

def swapPairs1(head) :

    # Special judgment
    if head is None: return None
    if head.next is None: return head

    dummy = point = ListNode()  Declare the header and build the list of nodes

    def swapTwoNodes(node1, node2, point) :
        Swap two node positions and concatenate them to the end of the result list.
        n2_next = node2.next
        point.next = node2
        node2.next = node1
        node1.next = n2_next  # switch node1's next to node2's children

    while head is not None:
        if head.next:  # If head.next is not empty, swap head and head.next
            if point.next is not None:  # If point.next is not empty, point the node to the lower node, which is used to concatenate the nodes swapped later
                point = point.next.next
            swapTwoNodes(head, head.next, point)
            head = head.next  Head. Next is a node that has not been swapped
        else:
            head = head.next  # If head.next is empty, point directly to next

    return dummy.next
Copy the code

The official way:

def swapPairs2(head) :
    """ iteration, official word """ "
    dummyHead = ListNode()
    dummyHead.next = head  Create a dummy node and point to the head
    temp = dummyHead  Swap two nodes after temp at a time
    while temp.next and temp.next.next:
        node1 = temp.next
        node2 = temp.next.next
        temp.next = node2
        node1.next = node2.next
        node2.next = node1
        temp = node1  # temp points to the location of node1 after the swap
    return dummyHead.next
Copy the code
Complexity analysis
  • Time complexity: O(n), where n is the number of nodes in the linked list. You need to update Pointers on each node.
  • Space complexity: O(1).

Method 2

Refer to the official answer. Main idea: you can exchange the nodes in the linked list in pairs in a recursive way. Recursion terminates when there are no nodes in the list, or only one node in the list, at which point swapping cannot be done.

def swapPairs3(head) :
    "" "recursive "" "
    if not head or not head.next: return head  # Special value judgment
    newhead = head.next  Record the next node of the header
    head.next = swapPairs2(newhead.next)  # swap the result of newhead.next as the next node of head
    newhead.next = head  # swap node, make head the next node of Newhead
    return newhead
Copy the code
Complexity analysis
  • Time complexity: O(n), where n is the number of nodes in the linked list. You need to update Pointers on each node.
  • Spatial complexity: O(n), where n is the number of nodes in the linked list. The space complexity depends primarily on the stack space for recursive calls.

The official answer