LeetCode-in-All
24. Swap Nodes in Pairs
Medium
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
Solution
using LeetCodeNet.Com_github_leetcode;
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int val=0, ListNode next=null) {
* this.val = val;
* this.next = next;
* }
* }
*/
public class Solution {
public ListNode SwapPairs(ListNode head) {
if (head == null) {
return null;
}
int len = GetLength(head);
return Reverse(head, len);
}
private int GetLength(ListNode curr) {
int cnt = 0;
while (curr != null) {
cnt++;
curr = curr.next;
}
return cnt;
}
// Recursive function to reverse in groups
private ListNode Reverse(ListNode head, int len) {
// base case
if (len < 2) {
return head;
}
ListNode curr = head;
ListNode prev = null;
ListNode next;
for (int i = 0; i < 2; i++) {
// reverse linked list code
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
head.next = Reverse(curr, len - 2);
return prev;
}
}