本文用到的链表python实现类如下：

class ListNode(object):

    def __init__(self, val):
        self.val = val
        self.next = None

    @staticmethod
    def fromlist(arr):
        dummy = ListNode(-1)
        head = ListNode(arr.pop(0))
        dummy.next = head
        while arr:
            head.next = ListNode(arr.pop(0))
            head = head.next
        return dummy.next

    def tolist(self):
        ret = [self.val]
        node = self.next
        while node:
            ret.append(node.val)
            node = node.next
        return ret

    def __getitem__(self, item):
        if not isinstance(item, int):
            return None
        ret, i = self, 0
        while ret:
            if i == item:
                return ret
            ret = ret.next
            i += 1
        return None

在O(1)时间删除链表节点

题目描述：给定链表的头指针和一个节点指针，在O(1)时间删除该节点。[Google面试题]

分析：本题与《编程之美》上的「从无头单链表中删除节点」类似。主要思想都是「狸猫换太子」，即用下一个节点数据覆盖要删除的节点，然后删除下一个节点。但是如果节点是尾节点时，该方法就行不通了。

代码如下：

def delete_node(node):
    if not node or not node.next:
        return
    node.val = node.next.val
    node.next = node.next.next

head = ListNode.fromlist([1,2,3,4,5])
delete_node(head[2])
assert head.tolist() == [1,2,4,5]

单链表的转置

题目描述：输入一个单向链表，输出逆序反转后的链表

分析：链表的转置是一个很常见、很基础的数据结构题了，非递归的算法很简单，用三个临时指针 pre、head、next 在链表上循环一遍即可。递归算法也是比较简单的，但是如果思路不清晰估计一时半会儿也写不出来吧。

下面是循环版本和递归版本的链表转置代码：

def reverse(head):
    p1 = head
    p2 = head.next
    while p2:
        tmp = p2.next
        p2.next = p1
        p1 = p2
        p2 = tmp
    head.next = None
    return p1

head = ListNode.fromlist([1,2,3,4,5])
reversed_head = reverse(head)
assert reversed_head.tolist() == [5,4,3,2,1]

def reverse(head):
    if head==None or head.next==None:
        return head
    new_head = reverse(head.next)
    head.next.next = head
    head.next = None
    return new_head

head = ListNode.fromlist([1,2,3,4,5])
reversed_head = reverse(head)
assert reversed_head.tolist() == [5,4,3,2,1]

求链表倒数第k个节点

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

分析：设置两个指针 p1、p2，首先 p1 和 p2 都指向 head，然后 p2 向前走 k 步，这样 p1 和 p2 之间就间隔 k 个节点，最后 p1 和 p2 同时向前移动，直至 p2 走到链表末尾。

代码如下：

def last_k_nodes(head, k):
    if k<0: return None slow,fast = head,head while k>0 and fast.next:
        fast = fast.next
        k -= 1
    if k>0:
        return None
    while fast and fast.next:
        fast = fast.next
        slow = slow.next
    return slow

head = ListNode.fromlist([1,2,3,4,5])
assert last_k_nodes(head, 0).val == 5
assert last_k_nodes(head, 1).val == 4
assert last_k_nodes(head, 4).val == 1
assert last_k_nodes(head, 5) is None

类似的题目有，删除链表倒数的第K个节点。

求链表的中间节点

题目描述：求链表的中间节点，如果链表的长度为偶数，返回中间两个节点的任意一个，若为奇数，则返回中间节点。

分析：此题的解决思路和第3题「求链表的倒数第 k 个节点」很相似。可以先求链表的长度，然后计算出中间节点所在链表顺序的位置。但是如果要求只能扫描一遍链表，如何解决呢？最高效的解法和第3题一样，通过两个指针来完成。用两个指针从链表头节点开始，一个指针每次向后移动两步，一个每次移动一步，直到快指针移到到尾节点，那么慢指针即是所求。

def find_middle(head):
    slow, fast = head, head
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
    return slow

head = ListNode.fromlist([1,2,3,4,5])
assert find_middle(head).val == 3
head = ListNode.fromlist([1,2,3,4,5,6])
assert find_middle(head).val in [3,4]

判断单链表是否存在环

题目描述：输入一个单向链表，判断链表是否有环？

分析：通过两个指针，分别从链表的头节点出发，一个每次向后移动一步，另一个移动两步，两个指针移动速度不一样，如果存在环，那么两个指针一定会在环里相遇。

代码如下：

def is_circle(head):
    slow, fast = head, head
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
        if fast is slow:
            return True
    return False

head = ListNode.fromlist([1,2,3,4,5])
assert is_circle(head) == False

circle_head = ListNode.fromlist([1,2,3])
circle = ListNode(0)
circle_head.next.next.next = circle
dummy = circle
for i in range(4, 7):
    circle.next = ListNode(i)
    circle = circle.next
circle.next = dummy
assert is_circle(circle_head) == True

找到环的入口点

题目描述：输入一个单向链表，判断链表是否有环。如果链表存在环，如何找到环的入口点？

解题思路： 由上题可知，按照 p2 每次两步，p1 每次一步的方式走，发现 p2 和 p1 重合，确定了单向链表有环路了。接下来，让p2回到链表的头部，重新走，每次步长不是走2了，而是走1，那么当 p1 和 p2 再次相遇的时候，就是环路的入口了。

为什么？：假定起点到环入口点的距离为 a，p1 和 p2 的相交点M与环入口点的距离为b，环路的周长为L，当 p1 和 p2 第一次相遇的时候，假定 p1 走了 n 步。那么有：

p1走的路径： a+b ＝ n；
p2走的路径： a+b+k*L = 2*n； p2 比 p1 多走了k圈环路，总路程是p1的2倍

根据上述公式可以得到 k*L=a+b=n显然，如果从相遇点M开始，p1 再走 n 步的话，还可以再回到相遇点，同时p2从头开始走的话，经过n步，也会达到相遇点M。

显然在这个步骤当中 p1 和 p2 只有前 a 步走的路径不同，所以当 p1 和 p2 再次重合的时候，必然是在链表的环路入口点上。

代码如下：

def find_loop_idx(head):
    if not head or not head.next: return None
    slow, fast = head, head
    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
        if fast is slow:
            break
    if fast is not slow: # circle dont exists
        return None
    fast = head
    while fast and fast.next:
        fast = fast.next
        slow = slow.next
        if fast is slow:
            break
    return fast

circle_head = ListNode.fromlist([1,2,3])
circle = ListNode(-9)
circle_head.next.next.next = circle
dummy = circle
for i in range(4, 7):
    circle.next = ListNode(i)
    circle = circle.next
circle.next = dummy

assert find_loop_idx(circle_head).val == -9

判断两个链表是否相交

题目描述：给出两个单向链表的头指针（如下图所示）

比如h1、h2，判断这两个链表是否相交。这里为了简化问题，我们假设两个链表均不带环。

解题思路：

• 直接循环判断第一个链表的每个节点是否在第二个链表中。但，这种方法的时间复杂度为O(Length(h1) * Length(h2))。显然，我们得找到一种更为有效的方法，至少不能是O（N^2）的复杂度。
• 针对第一个链表直接构造hash表，然后查询hash表，判断第二个链表的每个节点是否在hash表出现，如果所有的第二个链表的节点都能在hash表中找到，即说明第二个链表与第一个链表有相同的节点。时间复杂度为为线性：O(Length(h1) + Length(h2))，同时为了存储第一个链表的所有节点，空间复杂度为O(Length(h1))。是否还有更好的方法呢，既能够以线性时间复杂度解决问题，又能减少存储空间？
• 转换为环的问题。把第二个链表接在第一个链表后面，如果得到的链表有环，则说明两个链表相交。如何判断有环的问题上面已经讨论过了，但这里有更简单的方法。因为如果有环，则第二个链表的表头一定也在环上，即第二个链表会构成一个循环链表，我们只需要遍历第二个链表，看是否会回到起始点就可以判断出来。这个方法的时间复杂度是线性的，空间是常熟。
• 进一步考虑“如果两个没有环的链表相交于某一节点，那么在这个节点之后的所有节点都是两个链表共有的”这个特点，我们可以知道，如果它们相交，则最后一个节点一定是共有的。而我们很容易能得到链表的最后一个节点，所以这成了我们简化解法的一个主要突破口。那么，我们只要判断两个链表的尾指针是否相等。相等，则链表相交；否则，链表不相交。所以，先遍历第一个链表，记住最后一个节点。然后遍历第二个链表，到最后一个节点时和第一个链表的最后一个节点做比较，如果相同，则相交，否则，不相交。这样我们就得到了一个时间复杂度，它为O((Length(h1) + Length(h2))，而且只用了一个额外的指针来存储最后一个节点。这个方法时间复杂度为线性O(N)，空间复杂度为O(1)，显然比解法三更胜一筹。

def is_crossed(a, b):
    if not a or not b:
        return False
    while a.next:
        a = a.next
    while b.next:
        b = b.next
    return a is b

a = ListNode.fromlist([1,2,3])
b = ListNode.fromlist([1])
crossed_nodes = ListNode(11)
crossed_nodes.next = ListNode(12)
crossed_nodes.next.next = ListNode(13)
a.next.next.next = crossed_nodes
b.next = crossed_nodes

assert is_crossed(a, b) == True
assert a.tolist() == [1,2,3,11,12,13]
assert b.tolist() == [1,11,12,13]

两链表相交的第一个公共节点

题目描述：如果两个无环单链表相交，怎么求出他们相交的第一个节点呢？

分析：采用对齐的思想。计算两个链表的长度 L1 , L2，分别用两个指针 p1 , p2 指向两个链表的头，然后将较长链表的 p1（假设为 p1）向后移动L2 – L1个节点，然后再同时向后移动p1 , p2，直到 p1 = p2。相遇的点就是相交的第一个节点。

def listnode_length(node):
    if not node: return 0
    ret, head = 1, node.next
    while head:
        ret += 1
        head = head.next
    return ret

def find_cross(a, b):
    len1 = listnode_length(a)
    len2 = listnode_length(b)
    diff_len = abs(len1-len2)-1
    shorter_node = a if len1<len2 else b while diff_len>0:
        shorter_node = shorter_node.next
        diff_len -= 1
    return shorter_node

a = ListNode.fromlist([1,2,3])
b = ListNode.fromlist([1])
crossed_nodes = ListNode(11)
crossed_nodes.next = ListNode(12)
crossed_nodes.next.next = ListNode(13)
a.next.next.next = crossed_nodes
b.next = crossed_nodes

assert find_cross(a, b).val == 11

链表有环，如何判断相交

题目描述：上面的问题都是针对链表无环的，那么如果现在，链表是有环的呢?上面的方法还同样有效么?

分析：如果有环且两个链表相交，则两个链表都有共同一个环，即环上的任意一个节点都存在于两个链表上。因此，就可以判断一链表上俩指针相遇的那个节点，在不在另一条链表上。

将链表以K个长度为单位进行翻转

剩余不足K长的部分保持不变，LeetCode上面有这道题目，参考 https://leetcode.com/problems/reverse-nodes-in-k-group/description/

例如，目标链表为: [1,2,3,4,5,6,7,8,9,10]

k=2时，返回 [2, 1, 4, 3, 6, 5, 8, 7, 10, 9]
k=3时，返回 [3, 2, 1, 6, 5, 4, 9, 8, 7, 10]

思路1：从头到尾依次翻转k个单位，然后判断最后一次翻转的个数不足k个的，再把最后尾巴几个翻转回去。

def reverseKGroup1(self, head, k):
    """
    :type head: ListNode
    :type k: int
    :rtype: ListNode
    """
    if k==1 or not head:
        return head
    curhead, newhead, curtail = head, head, None
    p1, p2, steps = head, head.next, 1
    
    while p2:
        tmp = p2.next
        p2.next = p1
        if curtail:
            curtail.next = p2
            
        steps += 1
        if steps == k:
            curhead.next = tmp
            if newhead is head: # 第一次翻转后的head做为最终的头
                newhead = p2
            curtail = curhead
            
            if not tmp:
                break

            steps = 1
            curhead = tmp
            p1 = tmp
            p2 = tmp.next
        else:
            if not tmp:
                break
            p1 = p2
            p2 = tmp
            
    # 最后不足k个数的，再翻转过来
    if steps != k:
        curhead.next = None
        curhead = curtail.next if curtail else p2
        if curhead:
            p1, p2 = curhead, curhead.next
            while p2:
                tmp = p2.next
                p2.next = p1
                p1 = p2
                p2 = tmp
            if curtail:
                curtail.next = p1
            curhead.next = None
    
    return newhead

if __name__ == '__main__':

    head = ListNode.fromlist([1,2,3,4,5,6,7,8,9,10,]) # 3,4,5,6,7,8,9,10,11,12
    new = reverseKGroup(head, 2)
    print new.tolist()

思路2：先判断目前的长度够不够k，不够就不用翻转，够的话再进行翻转。

def reverseKGroup(head, k):
    if k==1 or not head:
        return head
    dummy = jump = ListNode(-1)
    dummy.next = l = r = head
    
    while True:
        count = 0
        while r and count < k:
            r = r.next
            count += 1
        
        if count != k:
            break
        
        pre, cur = r, l
        for _ in range(k):
            cur.next, pre, cur = pre, cur, cur.next
        jump.next, jump, l = pre, l, r

    return dummy.next

思路3：递归法

def reverseKGroup(head, k):
    curr, count = head, 0
    while count < k and curr: # find the k+1 node
        curr, count = curr.next, count+1
    if count != k:
        return head

    # if k+1 node is found
    curr = reverseKGroup(curr, k)  # reverse list with k+1 node as head
    while count > 0: # reverse current k-group: 
        count -= 1
        tmp = head.next
        head.next = curr
        curr = head
        head = tmp

    head = curr
    return head

以某个值为界线分割链表

Partition算法，给定一个链表及数值x，新生成一个链表，使得链表左半部分全部小于x，右边部分大于等于x，且左右两边部分保持原有的顺序。

如输入 1->4->3->2->5->2 ， x = 3,
返回    1->2->2->4->3->5.

这个也是LeetCode上面的题目：https://leetcode.com/problems/partition-list/description/

解题思路是维护两个链表，第一个存储所有比x小的节点，第二个存储其它的节点，最后将两条链表连接起来。注意第二条链表的最后一个节点的next要设置成空，否则可能存在环。

def partition(head, x):
    dummy1, dummy2 = ListNode(-1), ListNode(-1)
    curr1, curr2 = dummy1, dummy2
    while head:
        if head.val < x:
            curr1.next = head
            curr1 = curr1.next
        else:
            curr2.next = head
            curr2 = curr2.next
        head = head.next
    curr1.next = dummy2.next
    curr2.next = None
    return dummy1.next

if __name__ == '__main__':
    head = ListNode.fromlist([1,4,3,2,5,2])
    new = partition(head, 3)
    assert new.tolist() == [1,2,2,4,3,5]

对一个链表进行排序

要求使用常量的空间复杂度。LeetCode题目：https://leetcode.com/problems/sort-list/description/

思路，采用Merge排序方法，把链表分成两半，递归对左右两半分别进行排序，再把排序好的两半进行merge。

def sort_listnode(head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    if not head or not head.next:
        return head
    slow = fast = head
    pre = None
    while fast and fast.next:
        pre = slow
        slow = slow.next
        fast = fast.next.next
    # 以slow前一个节点为分界，分为左右两半部分
    pre.next = None
    left = sort_listnode(head)
    right = sort_listnode(slow)
    # merge排序好的两部分
    return merge_listnode(left, right)

def merge_listnode(left, right):
    l = p = ListNode(-1)
    while left and right:
        if left.val < right.val:
            p.next = left
            left = left.next
        else:
            p.next = right
            right = right.next
        p = p.next
    if left:
        p.next = left
    if right:
        p.next = right
    return l.next

if __name__ == '__main__':
    head = ListNode.fromlist([1,4,3,9,2,5,2])
    new = sort_listnode(head)
    assert new.tolist() == [1,2,2,3,4,5,9]

检查链表是否为回文

解法1：反转并比较。
第一种解法是反转整个链表，然后比较反转链表和原始链表。若两者相同，则该链表为回文。
注意，在比较原始链表和反转链表时，其实只需比较链表的前半部分。若原始链表和反转链表的前半部分相同，那么，两者的后半部分肯定相同。

解法2：迭代法
要想探测链表的前半部分是否为后半部分反转而成，该怎么做呢？只需将链表前半部分反转，可以利用栈来实现。
我们需要将前半部分结点入栈。根据链表长度已知与否，入栈有两种方式。
若链表长度已知，可以用标准for迭代访问前半部分结点，将每个结点入栈。当然，要小心处理链表长度为奇数的情况。
若链表长度未知，则可利用上面的快慢runner方法迭代访问链表，找到中间位置。代码如下：

def is_palindrome(head):
    fast = head
    slow = head
    stack = []
    while fast and fast.next:
        stack.append(slow.val)
        fast = fast.next.next
        slow = slow.next

    if fast: # lenth is odd
        slow = slow.next

    while slow:
        if slow.val != stack.pop():
            return False
        slow = slow.next
    return True

if __name__ == '__main__':
    arr = [1, 3, 1, 4, 5, 3, 6, 2]
    node = ListNode.fromlist(arr)
    assert is_palindrome(node) == False
    arr = [1, 3, 1, 4, 1, 3, 1]
    node = ListNode.fromlist(arr)
    assert is_palindrome(node) == True
    arr = [1, 3, 1, 4, 4, 1, 3, 1]
    node = ListNode.fromlist(arr)
    assert is_palindrome(node) == True