Good questions —— 链表篇

概述：本文记录了刷题过程中与链表相关的优质题目及解题思路

反转链表

（需要完全掌握递归和非递归写法）

（1）迭代

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
迭代方法
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre=nullptr;
        ListNode* cur=head;
        while(cur!=nullptr){
            ListNode* temp = cur->next;  //暂存后继节点
            cur->next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;//注意返回的是pre而不是cur，cur在出循环后是nullptr
    }
};

（2）递归

//递归
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return recur(head, nullptr);           // 调用递归并返回
    }
private:
    ListNode* recur(ListNode* cur, ListNode* pre) {
        if (cur == nullptr) return pre;        // 终止条件
        ListNode* res = recur(cur->next, cur); // 递归后继节点
        cur->next = pre;                       // 修改节点引用指向
        return res;                            // 返回反转链表的头节点
    }
};

复杂链表的复制

思路：

（1）哈希表存储所有原节点到新复制的节点的映射

（2）原地复制（在链表每个节点后复制一个新节点），再处理所有的next和random指针，最后断开原链表与新链表之间的连接

重排链表

时间O(n), 空间O(1)思想：

（1）找到链表中间节点，并断开

（2）反转后半部分的链表

（3）合并两个链表

k个一组反转链表

思想：

（1）设计一个反转[head,tail]区间的节点的函数，并返回反转后的头和尾

（2）注意保存头结点的前一节点，用于连接局部反转后的链表