Delete the Nth node from the bottom of the linked list

LeetCode 19. Delete the Nth node from the bottom of the linked list

/**
 * 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* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *p = dummy, *q = dummy;

        while(n--) p = p->next;
        while(p->next){<!-- -->
            p = p->next;
            q = q->next;
        }
        q->next = q->next->next;
        return dummy->next;
    }
};

Key

• Create a virtual node dummy, pointing to head
• Use double pointers p, q
• p is n positions ahead of q
• When p points to the last node, q points to the immediate predecessor of the node to be deleted.

leetcode 237. Delete nodes in the linked list

/**
 * Definition for singly-linked list.
 * struct ListNode {
 * int val;
 * ListNode *next;
 * ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {<!-- -->
public:
    void deleteNode(ListNode* node) {<!-- -->
        node->val = node->next->val;
        node->next = node->next->next;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 * int val;
 * ListNode *next;
 * ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {<!-- -->
public:
    void deleteNode(ListNode* node) {<!-- -->
        *node = *(node->next);
    }
};

leetcode 83. Delete duplicate elements in sorted linked list

/**
 * 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* deleteDuplicates(ListNode* head) {<!-- -->
        if(! head)
            return head;
        ListNode* p = head;
        while(p->next){<!-- -->
            if(p->val == p->next->val)
                p->next = p->next->next;
            else p = p->next;
        }
        return head;
    }
};

leetcode 61. Rotating linked list

/**
 * 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* rotateRight(ListNode* head, int k) {<!-- -->
        if(!head || !head->next || !k)
            return head;
        ListNode* p = head;
        int n = 1;
        while(p->next){<!-- -->
            p = p->next;
            n + + ;
        }

        k %= n;
        if(!k) return head;

        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        p = dummy;
        ListNode* q = dummy;
        while(k--) p = p->next;
        while(p->next){<!-- -->
            p = p->next;
            q = q->next;
        }
        dummy->next = q->next;
        p->next = head;
        q->next = NULL;
        return dummy->next;
    }
};

Note

• There are bugs in the last three items when modifying pointer statements.
• Therefore, special situations must be handled at the front of the program
  1 When the linked list has only one node
2 k % n = 0
• main idea

1. Rotate k times, that is, put the last k nodes of the linked list as a whole at the head of the list
2. Therefore, use double pointers to find the last k nodes

/**
 * 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* rotateRight(ListNode* head, int k) {<!-- -->
        if(!head)
            return head;
        ListNode* p = head;
        int n = 1;
        while(p->next){<!-- -->
            p = p->next;
            n + + ;
        }

        k %= n;

        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        p = dummy;
        ListNode* q = dummy;
        while(k--) p = p->next;
        while(p->next){<!-- -->
            p = p->next;
            q = q->next;
        }
        p->next = head;
        head = q->next;
        q->next = NULL;
        return head;
    }
};

leetcode 24. Exchange nodes in the linked list pairwise

/**
 * 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)
            return head;
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* p = dummy;
        ListNode* q = head;
        while(q & amp; & amp; q->next){<!-- -->
            p->next = q->next;
            q->next = q->next->next;
            p->next->next = q;
            p = q;
            q = q->next;
        }
        return dummy->next;
    }
};

• Case ①: The table is empty, return directly
• Case ②: The number of elements in the table is an odd number, and the last one is not processed, so the successor of q and q is not empty in the while loop condition.
• Situation ③: General situation