Question

Formatted question description: https://leetcode.ca/all/24.html

24	Swap Nodes in Pairs

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

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

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

@tag-linkedlist
 */

/*
could be extended, swap k sublist

eg: k=3, 2->1->4->3->2->1->4->3

2->1->4->3->2->1->4->3  ===>  (2->1->4)->(3->2->1)->4->3  ===>  4->1->2->1->2->3->4->3

method: swapKNodes(ListNode head, int k)

then just extract a method of reversing a sublist, and update to next k nodes

Algorithm

Create a dummyHead that occurs before head, that is, dummyHead.next = head. Each time take the two next nodes, and modify the next elements that each node points to. Suppose the current node is temp, and the next two nodes are node1 and node2 respectively, that is, node1 = temp.next and node2 = temp.next.next.

If node1 == null or node2 == null, then the end of the list is reached, so stop the process. Otherwise, change the nodes as follows. Let temp.next = node2, node1.next = node2.next, and node2.next = node1. After these steps, node1 and node2 are swapped. Move temp two steps forward (which should point to node1 after moving two steps), and do swapping for the next nodes. Finally, return dummyHead.next.

Code

Java

public class Swap_Nodes_in_Pairs {

    public static void main(String[] args) {

        Swap_Nodes_in_Pairs out = new Swap_Nodes_in_Pairs();
        Solution s = out.new Solution();
    }

    public class Solution {
        public ListNode swapPairs(ListNode head) {
//			if (head == null) { // this will not pass while loop below
//				return head;
//			}

            ListNode dummy = new ListNode(0);
            dummy.next = head;

            ListNode prev = dummy;

            // if only one node left, then no swap
            while (prev.next != null && prev.next.next != null) {

                ListNode first = prev.next;
                ListNode second = first.next;

                ListNode third = second.next;

                // swap
                prev.next = second;
                second.next = first;
                first.next = third;

                prev = prev.next.next;
            }

            return dummy.next;
        }
    }
}

// OJ: https://leetcode.com/problems/swap-nodes-in-pairs/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode h, *tail = &h;
        while (head && head->next) {
            auto p = head, q = head->next;
            head = q->next;
            q->next = p;
            tail->next = q;
            tail = p;
        } 
        tail->next = head;
        return h.next;
    }
};

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
  def swapPairs(self, head):
    """
    :type head: ListNode
    :rtype: ListNode
    """

    def reverseList(head, k):
      pre = None
      cur = head
      while cur and k > 0:
        tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp
        k -= 1
      head.next = cur
      return cur, pre

    if not head or not head.next:
      return head
    ret = head.next
    p = head
    pre = None
    while p:
      next, newHead = reverseList(p, 2)
      if pre:
        pre.next = newHead
      pre = p
      p = next
    return ret

24 - Swap Nodes in Pairs

Question

Algorithm

Code

All Problems

All Solutions