Swap Nodes in Pairs Problem


Description

LeetCode Problem 24.

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:

1
2
Input: head = [1,2,3,4]
Output: [2,1,4,3]

Example 2:

1
2
Input: head = []
Output: []

Example 3:

1
2
Input: head = [1]
Output: [1]

Constraints:

  • The number of nodes in the list is in the range [0, 100].
  • 0 <= Node.val <= 100


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if ((head == NULL) || (head->next == NULL))
            return head;
        ListNode* odd = head;
        ListNode* even = head->next;
        head = head->next;
        ListNode* tmp;
        
        while (even->next != NULL) {
            tmp = even->next;
            even->next = odd;
            if (tmp->next != NULL) {
                odd->next = tmp->next;
                odd = tmp;
                even = tmp->next;
            } else {
                odd->next = tmp;
                break;
            }
        }
        if (even->next == NULL) {
            even->next = odd;
            odd->next = NULL;
        }
        
        return head;
    }
};




Related Posts

Flatten Binary Tree To Linked List Problem

LeetCode 114. Given the root of a binary tree, flatten...

Remove Duplicates from Sorted List Problem

LeetCode 83. Given the head of a sorted linked list,...

Rotate List Problem

LeetCode 61. Given the head of a linked list, rotate...

Reverse Nodes in k-Group Problem

LeetCode 25. Given a linked list, reverse the nodes of...

Swap Nodes in Pairs Problem

LeetCode 24. Given a linked list, swap every two adjacent...