链表¶

链表常常碰到的问题有：

链表排序
链表删除：如删除链表中的 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);

解题思路

暴力
空间换时间，用一个 HashMap
快慢指针：使用两个指针 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)，以复制一个复杂链表。

这个题目难点在于：