Question

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

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.)

Example 1:

Input: head = [1,2,3,4]
Output: [2,1,4,3]

Example 2:

Input: head = []
Output: []

Example 3:

Input: head = [1]
Output: [1]

Constraints:

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

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

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;
        }
    }
}

############

/**
 * 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) {
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy, cur = head;
        while (cur != null && cur.next != null) {
            ListNode t = cur.next;
            cur.next = t.next;
            t.next = cur;
            pre.next = t;
            pre = cur;
            cur = cur.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:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        dummy = ListNode(next=head)
        pre, cur = dummy, head
        while cur and cur.next:
            t = cur.next
            cur.next = t.next
            t.next = cur
            pre.next = t
            pre, cur = cur, cur.next
        return dummy.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

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	res := swapPairs(head.Next.Next)
	p := head.Next
	p.Next, head.Next = head, res
	return p
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function swapPairs(head: ListNode | null): ListNode | null {
    const dummy = new ListNode(0, head);
    let cur = dummy;
    while (cur.next != null && cur.next.next != null) {
        const a = cur.next;
        const b = cur.next.next;
        [a.next, b.next, cur.next] = [b.next, a, b];
        cur = cur.next.next;
    }
    return dummy.next;
}

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function (head) {
    const dummy = new ListNode(0, head);
    let pre = dummy;
    let cur = head;
    while (cur && cur.next) {
        const t = cur.next;
        cur.next = t.next;
        t.next = cur;
        pre.next = t;
        pre = cur;
        cur = cur.next;
    }
    return dummy.next;
};

# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val = 0, _next = nil)
#         @val = val
#         @next = _next
#     end
# end
# @param {ListNode} head
# @return {ListNode}
def swap_pairs(head)
  dummy = ListNode.new(0, head)
  pre = dummy
  cur = head
  while !cur.nil? && !cur.next.nil?
      t = cur.next
      cur.next = t.next
      t.next = cur
      pre.next = t
      pre = cur
      cur = cur.next
  end
  dummy.next
end

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {
    pub fn swap_pairs(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut dummy = Some(Box::new(ListNode { val: 0, next: head }));
        let mut cur = dummy.as_mut().unwrap();
        while cur.next.is_some() && cur.next.as_ref().unwrap().next.is_some() {
            cur.next = {
                let mut b = cur.next.as_mut().unwrap().next.take();
                cur.next.as_mut().unwrap().next = b.as_mut().unwrap().next.take();
                let a = cur.next.take();
                b.as_mut().unwrap().next = a;
                b
            };
            cur = cur.next.as_mut().unwrap().next.as_mut().unwrap();
        }
        dummy.unwrap().next
    }
}

24 - Swap Nodes in Pairs

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions