刷完了Leetcode所有的链表简单—中等题，归纳一下用过的技巧。

一、快慢指针

相位差快慢

例题：实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

class Solution {
public:
    int kthToLast(ListNode* head, int k) {
        ListNode* fast = head, *slow = head;
        for(int i = 0; i < k - 1; i++)
        {
            fast = fast->next;
        }
        while(fast->next != NULL)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return slow->val;
    }
};

先让快指针走k-1步，再让快慢指针同速度前进。当快指针走到尾部，慢指针自然在倒数第k个节点。

步长快慢

例题：给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        if(head == NULL)
        {
            return NULL;
        }
        ListNode* fast = head;
        ListNode* low = head;
        while(fast->next != NULL)
        {
            low = low->next;
            fast = fast->next->next;
            if(fast == NULL)
            {
                break;
            }
        }
        return low;
    }
};

让快慢指针同时从头指针出发，快指针一次走两步，慢指针一次走一步，当快指针到达尾部，慢指针自然在正中间。

二、缓冲区

也就是另外建立存储数据的区域，例题：编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        ListNode* cur = head, *prev;
        int data[20001] = {0};
        while(cur != NULL)
        {
            if(data[cur->val] == 0)
            {
                data[cur->val]++;
                prev = cur;
                cur = cur->next;
            }
            else if(data[cur->val] == 1)
            {
                prev->next = cur->next;
                delete cur;
                cur = prev->next;
            }
        }
        return head;
    }
};

这里将每个数据放入对应的桶中，如果桶中已经有数据，自然判断出重复。

三、使用STL

同样也是使用了缓冲区，不过stl的一些方法可以大大简便操作

使用vector

例题：给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

class Solution {
public:
        void reorderList(ListNode* head) {
            if (!head) return;
            vector<ListNode*> vec;
            ListNode* cur = head;

            while (cur) {
                vec.push_back(cur);
                cur = cur->next;
            }

            int left = 0;
            int right = vec.size() - 1;
            while (left < right) {
                vec[left]->next = vec[right];
                vec[right--]->next = vec[++left];
            }
            vec[left]->next = nullptr;
        }
};

vector简便了取未操作过的首、尾节点的方法

使用stack

例题：多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构。给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。

class Solution {
public:
    Node* flatten(Node* head) {
        if (!head) return head;
        stack<Node*> n;
        Node* p = head, *temp;
        while (true)
        {
            while(true)
            {
                if (p->child)
                {
                    if (p->next)
                        n.push(p->next);
                    p->next = p->child;
                    p->next->prev = p;
                    p->child = NULL;
                }
                if(!(p->next))
                    break;
                p = p->next;
            }
            if (n.empty())
                break;
            temp = p;
            p = n.top();
            n.pop();
            temp->next = p;
            p->prev = temp;
        }
        return head;
    }
};

使用了stack保证了后进先出，使得扁平化从最分支到主枝进行。

使用map

map确保了键值对的唯一性，可以快速解决重复值问题。例题：给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。删除完毕后，请你返回最终结果链表的头节点。

class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {
        map<int, ListNode*> map;
        int sum = 0;
        ListNode* dummy = new ListNode(0), *cur = dummy;
        dummy->next = head;
        while (cur)
        {
            sum += cur->val;
            map[sum] = cur;
            cur = cur->next;
        }
        for(cur = dummy, sum = 0; cur; cur = cur->next)
        {
            sum += cur->val;
            if (map.find(sum) != map.end())
                cur->next = map[sum]->next;
        }
        return dummy->next;
    }
};

从头开始计算每到达一个节点时，前面所有节点值的总和，并且存在map中，如果有一个序列和为0，那么必有两个总和相等。再一次遍历时，如果某个总和在map中但不是当前节点，那么map中对应的节点和当前节点之间的和必定是0.

四、递归

链表的节点是相似的，可以使用递归解决。例题：给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if(!head) return NULL;
        if(head->val == val) return head->next;
        head->next = deleteNode(head->next,val);
        return head;
    }
};

通过递归，从头结点开始，下一个节点等于删除的只便跳过，重新连接链表。

五、补齐链表

当操作的两个链表长度不等时，可以先补齐至相同长度再操作。

例题：给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。你可以假设除了数字 0 之外，这两个数字都不会以零开头。

void addLinkList(struct ListNode* l1, struct ListNode* l2,int *cout)
{       
        if(l1==NULL||l2==NULL)
            return;
        if(l1->next!=NULL&&l2->next!=NULL)
            addLinkList(l1->next,l2->next,cout);
        int Sum=l1->val+l2->val+*cout;
        if(Sum>=10)
        {
            *cout=1;
            l1->val=Sum%10;
        }
        else
        {
            *cout=0;
            l1->val=Sum;
        }
        return;
}

六、原地修改

当复制的链表具有其他信息，不便于直接复制时，可以先原地复制，再间隔地挑出来。

例题：请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head) return NULL;
        Node* cur = head, *prev, *newhead;
        while(cur)
        {
            Node* newNode = new Node(cur->val);
            newNode->random = cur->random;
            newNode->next = cur->next;
            cur->next = newNode;
            cur = cur->next->next;
        }
        prev = head;
        newhead = head->next;
        while(prev)
        {
            cur = prev->next;
            if(cur->random)
                cur->random = cur->random->next;
            prev = prev->next->next;
        }
        prev = head;
        while(prev)
        {
            cur = prev->next;
            prev->next = prev->next->next;
            prev = prev->next;
            cur->next = prev ? prev->next : NULL;
        }
        return newhead;
    }
};

七、结合其他算法

例如结合BFS、DFS等搜索办法，DP、DC等优化算法等等