Swap pairs in Linked List

Given a linked list, swap every two adjacent nodes and return its head.

Example

Given 1->2->3->4, you should return the list as 2->1->4->3.

Challenge

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Think

  • Record next two node: dummy pre -> A -> B -> C.
  • Get C as next, change pre.next to B(head.next), B.next to A(head) and A(head.next) to C.
  • Do while loop when head and head.next are both not null node

Solution

public class Solution {
    /**
     * @param head a ListNode
     * @return a ListNode
     */
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;

        while(head != null && head.next != null) {

            ListNode next = head.next.next;
            pre.next = head.next;
            pre.next.next = head;
            pre = head;
            head.next = next;
            head = next;
        }
        return dummy.next;
    }
}

results matching ""

    No results matching ""