2 链表.md

链表

链表常常碰到的问题有：

• 链表排序
• 链表删除 ： 如删除链表中的p节点,在p节点前面插入节点q， 要求O(1)复杂度
• 2个链表 相交,合并
• 链表反转
• 链表中是否有环

链表结点定义如下：

struct ListNode
{
  int m_nKey;
  ListNode* m_pNext;
};

常用解题思路

• 双指针
• 3指针
• 快慢指针

输出链表中倒数第k个节点

题目：输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。

思路一：2遍遍历，先遍历一遍链表算出 n 的值，然后再遍历链表计算第 n - k 个节点 思路二：双指针，一个指针先走k步，然后 两个指针一起同步往前走，前面先走的指针到链表尾部吧，后面的指针刚好是第k个节点

类似的题目还有

删除第k个节点 链表的中间结点 ： 使用「快慢指针」的技巧 ，慢指针 slow 前进一步，快指针 fast 就前进两步，这样，当 fast 走到链表末尾时，slow 就指向了链表中点。

给定单链表，检测是否有环。

int isLinkCicle(Link *head);

解题思路

1. 暴力
2. 空间换时间，用一个HashMap
3. 快慢指针： 使用两个指针p1,p2从链表头开始遍历，p1每次前进一步，p2每次前进两步。如果p2到达链表尾部，说明无环，否则p1、p2必然会在某个时刻相遇(p1==p2)，从而检测到链表中有环。

链表反转

思路一：迭代，三个指针，遍历一遍(0(n)复杂度 思路一：递归实现，较难理解

迭代实现

递归实现

ListNode reverse(ListNode head) {
    if (head.next == null) return head;
    ListNode last = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return last;
}

从尾到头输出链表

输入一个链表的头结点，从尾到头反过来输出每个结点的值。链表结点定义如下：

思路一： 辅助栈，需要一个栈空间
思路二： 反转链表，然后遍历
思路三： 递归实现，将printf语句放在递归调用后面。果然妙极。。

复杂链表的复制

题目：有一个复杂链表，其结点除了有一个m_pNext指针指向下一个结点外，还有一个m_pSibling指向链表中的任一结点或者NULL。其结点的C++定义如下：

struct ComplexNode
{
  int m_nValue;
  ComplexNode* m_pNext;
  ComplexNode* m_pSibling;
};

下图是一个含有5个结点的该类型复杂链表。图中实线箭头表示m_pNext指针，虚线箭头表示m_pSibling指针。为简单起见，指向NULL的指针没有画出。
请完成函数ComplexNode* Clone(ComplexNode* pHead)，以复制一个复杂链表。

这个题目难点在于：