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