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

Middle Of The Linked List Problem

LeetCode 876. Given the head of a singly linked list,...

Linked List Components Problem

LeetCode 817. You are given the head of a linked...

Split Linked List In Parts Problem

LeetCode 725. Given the head of a singly linked list...

All O'One Data Structure Problem

LeetCode 432. Design a data structure to store the strings...

Add Two Numbers II Problem

LeetCode 445. You are given two non-empty linked lists representing...