Welcome to Subscribe On Youtube

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

All Problems

All Solutions