給定一個帶有頭節點的單鏈表，如何將其逆序，也就是說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