🗓️Day 04 – This is what you need to write.
Topics: This is what you need to write.
Problem solved:
#24 - Swap Nodes in Pairs
#19 - Remove Nth Node from End of List
#142 Linked list Cycle II

---

🧩Problem solution – 24. Swap Nodes in Pairs

link

💡Problem description

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]

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

Constraints:

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

🧭Thought Process

It’s easy to swap two nodes, but we should think about the impact of this action on the entire linked list. It is how to connect the new pair with the previous one and the last one. The easiest way is that we always use two pointers to mark the preNode and the lastNode.

💻Code Implementation

/**
 * 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* swapx = head;
        ListNode* swapy = head->next;
        ListNode* res = swapy;
        ListNode* temp;
        ListNode* pre = NULL;
        while(1){
            temp = swapy->next;
            swapx->next = temp;
            swapy->next = swapx;
            if(pre!=NULL)
                pre->next = swapy;
            pre = swapx;
            swapx = temp;
            if(swapx==NULL)
                break;
            swapy = swapx->next;
            if(swapy==NULL)
                break;
        }
        return res;
    }
};

⏱️Complexity Analysis

• Time complexity: O(n)
• Space complexity: O(1)

🧩Problem solution – 19. Remove Nth Node from End of List

link

💡Problem description

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:

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

Example 2:
Input: head = [1], n = 1
Output: []

Example 3:
Input: head = [1,2], n = 1
Output: [1]

Constraints:

The number of nodes in the list is sz.
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

🧭Thought Process

Imagine there is a rabbit and a turtle. At first, the rabbit runs faster than the turtle so that when the rabbit reaches the location N, the turtle is still at the beginning. The rabbit thought it will win definitely, so it keep the same speed as the turtle. That makes the distance between rabbit and the turtle is always N. So we the rabbit gets the destination, the turtle gets the Nth node from the end.

💻Code Implementation

/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        ListNode* rabbit, *turtle;
        ListNode* nothead = new ListNode(0);
        nothead->next = head;
        rabbit = nothead;
        int i = n+1;
        turtle = rabbit;
        while(i--){
            turtle = turtle->next;
        }
        if(turtle==NULL)
            return head->next;
        while(turtle!=NULL){
            rabbit = rabbit->next;
            turtle = turtle->next;
        }
        turtle = rabbit->next;
        rabbit->next = turtle->next;
        return head;
    }
};

⏱️Complexity Analysis

• Time complexity: O(n)
• Space complexity: O(1)

🧩Problem solution – 142. Linked list Cycle II

link

💡Problem description

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.
Do not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.