“This is the 21st day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

1, the title

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.

Example 1:

Input: head = [1,2,3,4] output: [2,1,4,3]Copy the code

Example 2:

Input: head = [] Output: []Copy the code

Example 3:

Input: head = [1] Output: [1]Copy the code

Tip:

  • The number of nodes in the linked list is in range[0, 100] 内
  • 0 <= Node.val <= 100

2, train of thought

(Analog)O(n)O(n) O(n)

Given a linked list, we are asked to swap adjacent nodes in pairs and return the swapped list. Since there may be changes to the head node, we need to create a dummy head node pointing to the original head node.

Simulation iteration is carried out according to the meaning of the question, and two adjacent nodes are exchanged in pairs, as shown in the figure below:

Detailed explanation of the specific process:

  • P = dummy, a = p->next, b = a->next

  • P ->next = b (p->next = b)

  • A ->next = b->next

  • B ->next = a

    After the above operation, we have successfully swapped nodes A and B, and then set P to point to node A, repeat the above operation.

  • 5. Finally, return the next node of the virtual head node

Time complexity analysis: O(n)O(n)O(n), where NNN is the number of nodes in the linked list.

C++ code

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode*  dummy = new ListNode(- 1);  // Virtual head node
        dummy->next = head;
        for(auto p = dummy; p->next && p->next->next; )
        {
            auto a = p->next, b = a->next;
            p->next = b;
            a->next = b->next;
            b->next = a;
            p = a;
        }
        returndummy->next; }};Copy the code

4. Java code

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        for(ListNode p = dummy; p.next ! =null&& p.next.next ! =null;)
        {
            ListNode a = p.next;	// Virtual head node
            ListNode b = a.next;
            p.next = b;
            a.next = b.next;
            b.next = a;
            p = a;
        }
        returndummy.next; }}Copy the code

Swap nodes in a linked list in pairs