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