LeetCode Problem 206: Reverse Linked List

Problem Description:

Solution: Using a two-pointer approach with previous and current pointers, iteratively modify pointer directions. Pay atttention to the loop termination condition; return the previous pointer as the new head node.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int value;
 *     ListNode *nextNode;
 *     ListNode() : value(0), nextNode(nullptr) {}
 *     ListNode(int val) : value(val), nextNode(nullptr) {}
 *     ListNode(int val, ListNode *next) : value(val), nextNode(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* previous = nullptr;
        ListNode* current = head;
        while (current != nullptr) {
            ListNode* nextNode = current->nextNode;
            current->nextNode = previous;
            previous = current;
            current = nextNode;
        }
        return previous;
    }
};

LeetCode Problem 24: Swap Nodes in Pairs

Problem Description:

Approach: Use a dummy head node and diagram the operation sequence.

Solution:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int value;
 *     ListNode *nextNode;
 *     ListNode() : value(0), nextNode(nullptr) {}
 *     ListNode(int val) : value(val), nextNode(nullptr) {}
 *     ListNode(int val, ListNode *next) : value(val), nextNode(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode();
        dummyHead->nextNode = head;
        ListNode* current = dummyHead;
        while (current->nextNode != nullptr && current->nextNode->nextNode != nullptr) {
            // Skip if only one node remains
            ListNode* firstNode = current->nextNode;
            ListNode* secondNode = current->nextNode->nextNode;
            ListNode* thirdNode = current->nextNode->nextNode->nextNode;

            current->nextNode = secondNode; // Step 1
            secondNode->nextNode = firstNode; // Step 2
            firstNode->nextNode = thirdNode; // Step 3

            current = current->nextNode->nextNode;
        }
        ListNode* result = dummyHead->nextNode;
        delete dummyHead;
        return result;
    }
};

LeetCode Problem 19: Remove Nth Node From End of List

Problem Description:

Solutino: Two-pointer technique with fast and slow pointers. The slow pointer lags behind the fast pointer by n+1 steps. When the fast pointer reaches nullptr, the slow pointer points to the node preceding the one to be removed.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int value;
 *     ListNode *nextNode;
 *     ListNode() : value(0), nextNode(nullptr) {}
 *     ListNode(int val) : value(val), nextNode(nullptr) {}
 *     ListNode(int val, ListNode *next) : value(val), nextNode(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode();
        dummyHead->nextNode = head;
        ListNode* slow = dummyHead;
        ListNode* fast = dummyHead;
        while (n-- && fast->nextNode != nullptr) {
            fast = fast->nextNode;
        }
        fast = fast->nextNode;
        while (fast != nullptr) {
            slow = slow->nextNode;
            fast = fast->nextNode;
        }
        ListNode* nodeToDelete = slow->nextNode;
        slow->nextNode = slow->nextNode->nextNode;
        delete nodeToDelete;
        ListNode* result = dummyHead->nextNode;
        delete dummyHead;
        return result;
    }
};