24 Swap Nodes in Pairs ✅¶
Given a linked list, swap every two adjacent nodes and return its head.
Example:
Note:
Your algorithm should use only constant extra space. You may not modify the values in the list’s nodes, only nodes itself may be changed.
Ideas¶
Set a dummy node to simplify the operation, dummy next points to head.
- Initialize first as the first node
- Initialize second as the second node
- Initialize current to dummy
- first.next = second.next
- second.next = first
- current.next = second
- current move two grids
- repeat
Solution¶
Time complexity: \(O(n)\) Space complexity: \(O(1)\)
C# Solution (with two pointers)¶
namespace Algorithms.Medium
{
/* // Definition for singly-linked list.
public class ListNode
{
int val;
ListNode next; ListNode(int x) { val = x; }
} */
public class SwapPairs
{
public ListNode Swap(ListNode head)
{
if (head == null || head.next == null) return head;
var tempNode = new ListNode(-1);
tempNode.next = head;
head = tempNode;
while (head != null && head.next != null && head.next.next != null)
{
var n1 = head.next;
var n2 = n1.next;
n1.next = n2.next;
n2.next = n1;
head.next = n2;
head = n1;
}
return tempNode.next;
}
}
}
Version from Ideas¶
public ListNode Swap(ListNode head)
{
ListNode fakeHead = new ListNode(-1);
fakeHead.next = head;
ListNode node = fakeHead;
while (node != null && node.next != null && node.next.next != null)
{
ListNode first = node;
ListNode second = node.next;
ListNode third = node.next.next;
first.next = third;
second.next = third.next;
third.next = second;
node = second;
}
return fakeHead;
}
}
Related Problems¶
-
- Sort List
-
- Remove Linked List Elements