给定一个带有头节点的单链表，如何将其逆序，也就是说head->a->b->c,变为head->c->b->a？

难点：这个需要了解链表的结构，每一个链表除了存储自身的元素之外，还会存储下一个结点的地址，所以要想遍历链表需要从头结点开始，还要注意一旦要是修改了当前结点存储的下一节点的地址，如果我们不使用一个变量记录这个地址，那么后面的链表就会丢失了，所以我们时时刻刻都不能忘记，当前结点的下一个结点的地址。

时间复杂度为O(N)

解决方法：插入法

核心思想是遍历链表，每遍历到一个结点就将其插入到头节点之后，作为头结点之后的第一个结点,比如遍历到b，那么此时它需要把b拿出来放到head后面，并且将a的后继结点的改为c，此时链表变为head->b->a->c,这样遍历完一遍之后就可以了，不用第二遍，而且不需要额外的地址。

代码实现：

class ListNode():
    def __init__(self):        self.data=None        self.next=next
def reverse(ListNode):
    if ListNode is None and ListNode.next is None:
        return
    #获取第二个（当前）    cur=ListNode.next.next
    ListNode.next.next=None
    nextNode=None    while cur is not None:
        nextNode=cur.next
        cur.next=ListNode.next
        ListNode.next=cur
        cur=nextNodeif __name__ =="__main__" :
    LNode=ListNode()    p=LNode    LNode.data=None    LNode.next=None
    i=1
    while i<=10:
        L=ListNode()        L.data=i        L.next=None
        p.next=L
        p=L        i=i+1
    cur=LNode.next
    while cur is not None:
        print(cur.data)
        cur=cur.next
    reverse(LNode)
    print("反转后")
    cur=LNode.next
    while cur is not None:
        print(cur.data)
        cur=cur.next

逆序输出链表

给定一个链表，然后逆序输出，比如有一个链表head->a->b->c，那么此时我们希望输出c，b，a

我们可以使用递归的形式，（a，b，c）先输出(b,c),然后(b,c)先输出c

时间复杂度O(N)

class Node():
    def __init__(self):
        self.next=None
        self.data=Nonedef  ReserverPrint(List):    if List is None:
        return
    ReserverPrint(List.next)    print(List.data)if __name__=="__main__":
    LNode=Node()    p=LNode    i=1
    while i<10:
        l=Node()        l.data=i        l.next=None
        p.next=l        p=l        i+=1
    cur=LNode.next    while cur is not None:
        print(cur.data)        cur=cur.next    #反转输出
    print("反转输出")
    ReserverPrint(LNode.next)

对链表进行重新排序

现在有一个链表为head->1->2->3->4->5->6->7,排序之后head->1->7->2->6->3->5->4

我们分析一下，可以看到实际上原始序列的前半部分并没有发生改变，而后半部分是逆序，然后将两个一个一个的插入了，所以说这个的核心是先将后半部分逆序，然后两个链表同时遍历，一个一个的最终形成新的排序链表

这个的意思就是说pre用于指向链表1的第一个结点，cur永远指向链表2的第二个结点，最后返回第一个结点就可以了

class Node():
    def __init__(self):        self.data=None        self.next=None
def firstmiddle(list):    if list is None or list.next is None:
        return list
    first=list    two=list    while two is not None and two.next is not None:
        pre_first=first        first=first.next
        two=two.next.next
    pre_first.next=None
    return first
def reverse(list):
    if list is None or list.next is None:
        return list
    cur=list.next
    pre=list    n_next=cur.next
    pre.next=None#这个意思是形成两部分，第一部分有第一个结点->None,第二部分以第二个结点cur直到最后
    while cur is not None:
        a=cur.next
        cur.next=pre
        pre=cur        cur=a    return pre
def Recorder(list):    cur1=list.next
    mid=firstmiddle(list.next)
    cur2=reverse(mid)
    while cur1.next is not None:
        a=cur1.next#存储cur1，然后再将cur1找回来
        cur1.next=cur2
        cur1=a        a=cur2.next
        cur2.next=cur1
        cur2=a    cur1.next=cur2
if __name__=="__main__":
    listNode=Node()    p=listNode    i=1
    while i<=10:
        l=Node()        l.data=i        l.next=None
        p.next=l
        p=l        i+=1
    Recorder(listNode)    cur=listNode.next
    while cur is not None:
        print(cur.data)
        cur=cur.next

找到一个链表的中间元素

从头开始遍历链表，设置两个指针，其中一个指针每次走两步，另外一个指针每次走一步，那么当走两步的这个只能走到头的时候，那么此时走第一步的这个指针就是指向的中间的元素

设置一个指针one，然后设置一个指针two，two每次走两步，然后one每次走一步，当two走到头之后，one就走到中间了。

如果链表结点数为奇数，那么此时的one就是中间结点，如果链表结点数为偶数，那么此时的one和接下来的一个结点就是中间结点

class Node():
    def __init__(self):
        self.next=None
        self.data=Nonedef FindMiddleNode(ListNode):    if ListNode is None or ListNode.next is None:
        return ListNode
    one=ListNode    two=ListNode    while two is not None and two.next is not None:
        one=one.next        two=two.next.next    return one
if __name__=="__main__":
    ListNode=Node()    p=ListNode    i=0
    while i<10:
        l=Node()        l.next=None
        l.data=i        p.next=l        p=l        i+=1
    cur=ListNode.next    #原始的列表顺序输出
    while cur is not None:
        print(cur.data)
        cur=cur.next
    mid=FindMiddleNode(ListNode.next)
    print(mid.data)#输出中间的元素

将两个链表依次合并，现在有一个l1链表a->b->c,还有一个l2链表1->2->3，然后依次合并，此时合并的链表为a->1->b->2->c->3

这个步骤是这样的，主要是将l1链表为主链，思想如下图所示：

class Node():
    def __init__(self):        self.data=None        self.next=None
if __name__=="__main__":
    one_listNode=Node()    one_p=one_listNode    two_listNode = Node()    two_p = two_listNode    i=1
    while i<=10:
        l=Node()        l.data=i        l.next=None
        one_p.next=l
        one_p=l        i+=1
    j=11
    while j<=20:
        l=Node()        l.data=j        l.next=None
        two_p.next=l
        two_p=l        j+=1
    one=one_listNode.next
    two=two_listNode.next
    a=None    while one.next is not None:
        a=one.next
        one.next=two
        one=a        a=two.next
        two.next=one
        two=a    one.next=two
    n=one_listNode.next
    while n is not None:
        print(n.data)
        n=n.next

找到一个链表的倒数第k个结点

我们可以设置两个指针，其中一个指针领先第二个指针k个元素，当第一个指针到链表结尾了，那么第一个指针就是链表的倒数第k个结点。这个只需要遍历一次链表，所以时间复杂度为O(N)

需要注意的是，我们需要时时刻刻地判断这个链表是否长度能够到k，如果本身就没有k个元素，那么倒数第k个元素也是没有意义的

class Node():
    def __init__(self):        self.next=None        self.data=None
def FindlastK(list,k):    if list is None or list.next is None:
        return
    i=0
    klist=list    first=list    #klist比first领先3个元素
    while i<k and klist is not None:
        klist=klist.next        i+=1
    if i<k:#如果领先不到3个元素，那么就会出现问题
        return
    while klist is not None:
        klist=klist.next        first=first.next    return first
if __name__=="__main__":
    list=Node()    p=list    i=1
    k=3
    n=None    while i<=7:
        n=Node()        n.data=i
        n.next=None        p.next=n        p=n        i+=1
    first=FindlastK(list,k)    print(first.data)

单链表向右旋转k个位置

这个意思是这样的，现在有一个单链表头结点->1->2->3->4->5->6->7,此时我们设置k=3，那么我们希望链表可以变为：头结点->5->6->7->1->2->3->4。

这个我们可以先找到倒数第k+1个结点slow，以及原始链表的尾结点fast，然后分割为两个链表，然后进行组合就完成了单链表向右旋转k个位置

class Node():
    def __init__(self):        self.next=None
        self.data=Nonedef  RotateK(list,K):    if list is None or list.next is None:
        return
    slow=list.next
    fast=list.next
    i=0
    tmpend=None    tmpstart=None    while i<=K and fast is not None:
        fast=fast.next
        i+=1
    if i<K:#根本没有k个原元素
        return
    while fast is not None:
        tmpend=fast        fast=fast.next
        slow=slow.next
        tmpstart=slow.next
    slow.next=None#断成两条链，第一条链头的list，尾是slow，第二条链头是tmpstart，尾是tmpend
    #print(slow.data)
    #print(tmpend.data)
    #print(tmpstart.data)
    tmpend.next=list.next
    list.next=tmpstart
if __name__=="__main__":
    list=Node()    p=list    i=1
    K=3
    while i<=7:
        n=Node()        n.data=i        n.next=None
        p.next=n
        p=n        i+=1
    RotateK(list,K)    a=list.next
    while a is not None:
        print(a.data)
        a=a.next