給定一個(gè)帶有頭節(jié)點(diǎn)的單鏈表，如何將其逆序，也就是說head->a->b->c,變?yōu)閔ead->c->b->a？

難點(diǎn)：這個(gè)需要了解鏈表的結(jié)構(gòu)，每一個(gè)鏈表除了存儲(chǔ)自身的元素之外，還會(huì)存儲(chǔ)下一個(gè)結(jié)點(diǎn)的地址，所以要想遍歷鏈表需要從頭結(jié)點(diǎn)開始，還要注意一旦要是修改了當(dāng)前結(jié)點(diǎn)存儲(chǔ)的下一節(jié)點(diǎn)的地址，如果我們不使用一個(gè)變量記錄這個(gè)地址，那么后面的鏈表就會(huì)丟失了，所以我們時(shí)時(shí)刻刻都不能忘記，當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的地址。

時(shí)間復(fù)雜度為O(N)

解決方法：插入法

核心思想是遍歷鏈表，每遍歷到一個(gè)結(jié)點(diǎn)就將其插入到頭節(jié)點(diǎn)之后，作為頭結(jié)點(diǎn)之后的第一個(gè)結(jié)點(diǎn),比如遍歷到b，那么此時(shí)它需要把b拿出來放到head后面，并且將a的后繼結(jié)點(diǎn)的改為c，此時(shí)鏈表變?yōu)閔ead->b->a->c,這樣遍歷完一遍之后就可以了，不用第二遍，而且不需要額外的地址。

代碼實(shí)現(xiàn)：

class ListNode():
    def __init__(self):        self.data=None        self.next=next
def reverse(ListNode):
    if ListNode is None and ListNode.next is None:
        return
    #獲取第二個(gè)（當(dāng)前）    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("反轉(zhuǎn)后")
    cur=LNode.next
    while cur is not None:
        print(cur.data)
        cur=cur.next

逆序輸出鏈表

給定一個(gè)鏈表，然后逆序輸出，比如有一個(gè)鏈表head->a->b->c，那么此時(shí)我們希望輸出c，b，a

我們可以使用遞歸的形式，（a，b，c）先輸出(b,c),然后(b,c)先輸出c

時(shí)間復(fù)雜度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    #反轉(zhuǎn)輸出
    print("反轉(zhuǎn)輸出")
    ReserverPrint(LNode.next)

對鏈表進(jìn)行重新排序

現(xiàn)在有一個(gè)鏈表為head->1->2->3->4->5->6->7,排序之后head->1->7->2->6->3->5->4

我們分析一下，可以看到實(shí)際上原始序列的前半部分并沒有發(fā)生改變，而后半部分是逆序，然后將兩個(gè)一個(gè)一個(gè)的插入了，所以說這個(gè)的核心是先將后半部分逆序，然后兩個(gè)鏈表同時(shí)遍歷，一個(gè)一個(gè)的最終形成新的排序鏈表

這個(gè)的意思就是說pre用于指向鏈表1的第一個(gè)結(jié)點(diǎn)，cur永遠(yuǎn)指向鏈表2的第二個(gè)結(jié)點(diǎn)，最后返回第一個(gè)結(jié)點(diǎn)就可以了

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#這個(gè)意思是形成兩部分，第一部分有第一個(gè)結(jié)點(diǎn)->None,第二部分以第二個(gè)結(jié)點(diǎn)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#存儲(chǔ)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

找到一個(gè)鏈表的中間元素

從頭開始遍歷鏈表，設(shè)置兩個(gè)指針，其中一個(gè)指針每次走兩步，另外一個(gè)指針每次走一步，那么當(dāng)走兩步的這個(gè)只能走到頭的時(shí)候，那么此時(shí)走第一步的這個(gè)指針就是指向的中間的元素

設(shè)置一個(gè)指針one，然后設(shè)置一個(gè)指針two，two每次走兩步，然后one每次走一步，當(dāng)two走到頭之后，one就走到中間了。

如果鏈表結(jié)點(diǎn)數(shù)為奇數(shù)，那么此時(shí)的one就是中間結(jié)點(diǎn)，如果鏈表結(jié)點(diǎn)數(shù)為偶數(shù)，那么此時(shí)的one和接下來的一個(gè)結(jié)點(diǎn)就是中間結(jié)點(diǎn)

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)#輸出中間的元素

將兩個(gè)鏈表依次合并，現(xiàn)在有一個(gè)l1鏈表a->b->c,還有一個(gè)l2鏈表1->2->3，然后依次合并，此時(shí)合并的鏈表為a->1->b->2->c->3

這個(gè)步驟是這樣的，主要是將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

找到一個(gè)鏈表的倒數(shù)第k個(gè)結(jié)點(diǎn)

我們可以設(shè)置兩個(gè)指針，其中一個(gè)指針領(lǐng)先第二個(gè)指針k個(gè)元素，當(dāng)?shù)谝粋€(gè)指針到鏈表結(jié)尾了，那么第一個(gè)指針就是鏈表的倒數(shù)第k個(gè)結(jié)點(diǎn)。這個(gè)只需要遍歷一次鏈表，所以時(shí)間復(fù)雜度為O(N)

需要注意的是，我們需要時(shí)時(shí)刻刻地判斷這個(gè)鏈表是否長度能夠到k，如果本身就沒有k個(gè)元素，那么倒數(shù)第k個(gè)元素也是沒有意義的

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領(lǐng)先3個(gè)元素
    while i<k and klist is not None:
        klist=klist.next        i+=1
    if i<k:#如果領(lǐng)先不到3個(gè)元素，那么就會(huì)出現(xiàn)問題
        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)

單鏈表向右旋轉(zhuǎn)k個(gè)位置

這個(gè)意思是這樣的，現(xiàn)在有一個(gè)單鏈表頭結(jié)點(diǎn)->1->2->3->4->5->6->7,此時(shí)我們設(shè)置k=3，那么我們希望鏈表可以變?yōu)椋侯^結(jié)點(diǎn)->5->6->7->1->2->3->4。

這個(gè)我們可以先找到倒數(shù)第k+1個(gè)結(jié)點(diǎn)slow，以及原始鏈表的尾結(jié)點(diǎn)fast，然后分割為兩個(gè)鏈表，然后進(jìn)行組合就完成了單鏈表向右旋轉(zhuǎn)k個(gè)位置

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個(gè)原元素
        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