2021-09-14

链表删除倒数第n个节点（双指针法）

/**
 * 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(0, head);
        ListNode* first = head;
        ListNode* second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first->next;
        }
        while (first) {
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};

重排链表

/**
 * 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:
    void reorderList(ListNode* head) {
    
    if(head != nullptr || head->next != nullptr){
    //第一步，找出分割点（中间点）
        ListNode * slowIndex = head;
        ListNode * fastIndex = head;
        while(fastIndex->next && fastIndex->next->next){
            slowIndex = slowIndex->next;
            fastIndex = fastIndex->next->next;
        }
    //第二步，把第二条链表翻转
        ListNode * cur = slowIndex->next;
        ListNode * pre = nullptr;
        ListNode * tmp;
        slowIndex->next = nullptr;
        while(cur){
            tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
    //第三步，把两个链表交替接起来
        //正链:head;    反链:pre
        ListNode * link1 = head;
        ListNode * link2 = pre;
        ListNode * temp1;
        ListNode * temp2;
        while(link1 && link2){
            temp1 = link1->next;
            temp2 = link2->next;
            link1->next = link2;
            link1 = temp1;
            link2->next = link1;
            link2 = temp2;
        }
    }
    }
};