Leetcode-24-Swap Nodes in Pairs

Swap Nodes in Pairs

leetcode: https://leetcode.com/problems/swap-nodes-in-pairs/

Description:

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)

Idea:

**solution **

Step1: set the dummy node, and set the current node = dummy, to traverse the list

Step2: assume the head as the first node.

Step3: set the temp node, and make it point to head.next.next node. because we need to store this node so that we can link the first node of two nodes(need to be swapped) to this node after the swap.

Step3: make current node point to the head.next(the second node of two nodes), then make the head.next.next to head(now, head.next is second node, so head.next.next need to point to the first node) to complete swap. then make head.next(after swap, the first node’s next node) point to temp to keep link after swap

Step4: make current to head and move head to next to continue traversal.

Step5: return dummy.next(the real list is after dummy node)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode dummy = new ListNode(0,head);
        ListNode current = dummy;
        ListNode temp;
        while(current.next!=null && current.next.next != null ){
            //set temporart node = head.next.next, so that we can know and link to the next node after swap two nodes
            temp = head.next.next;
            //Point the next node of the current node to the second node of the two nodes that need to be swapped
            current.next = head.next;
            //swap two nodes
            head.next.next = head;
            //after swap, link the fisrt node of two nodes that need to be swapped to the next node.
            head.next = temp;
            //move the current node to traverse
            current = head;
            //move the head to traverse;
            head = head.next;
        }
        //get the real list
        return dummy.next;
    }
}