• 定義
• 鏈表類型
• 代碼實(shí)現(xiàn)
• 題目 [反轉(zhuǎn)鏈表], [環(huán)形鏈表]

定義及操作
插入：類比火車車廂，先在要插入的位置斷開連接，將鏈表前端連接到要插入的位置上，在將新插入的尾部指向下一個(gè)位置。O(n)
刪除：將前一個(gè)數(shù)的指針直接指向下一個(gè)數(shù)。
找到第K個(gè)節(jié)點(diǎn)，需要O(n),因?yàn)橐樞虮闅v。

• 雙向鏈表：每一個(gè)節(jié)點(diǎn)可以向前或向后遍歷，可以到達(dá)鏈表頭或尾。由于要維護(hù)兩個(gè)節(jié)點(diǎn)，維護(hù)成本高一些。

#single link list
class ListNode(object):
    def __init__(self,x)：
        self.value = x
        self.next = None

#double link list
class ListNode(object):
    def __init__(self,x)：
        self.value = x
        self.pre = None
        self.last = None

#multiple link list, 
#eg. next[0] for left sub tree, next[1] for right sub tree -> binary tree
#Or next[] for the edge connect to current node -> graph
class ListNode(object):
    def __init__(self,x)：
        self.value = x
        self.next = []

完整實(shí)現(xiàn)代碼

class Node:

   def __init__(self,data,nextNode=None):
       self.data = data
       self.nextNode = nextNode

   def getData(self):
       return self.data

   def setData(self,val):
       self.data = val

   def getNextNode(self):
       return self.nextNode

   def setNextNode(self,val):
       self.nextNode = val

class LinkedList:

   def __init__(self,head = None):
       self.head = head
       self.size = 0

   def getSize(self):
       return self.size

   def addNode(self,data):
       newNode = Node(data,self.head)
       self.head = newNode
       self.size+=1
       return True
       
   def printNode(self):
       curr = self.head
       while curr:
           print(curr.data)
           curr = curr.getNextNode()

myList = LinkedList()
print("Inserting")
print(myList.addNode(5))
print(myList.addNode(15))
print(myList.addNode(25))
print("Printing")
myList.printNode()
#Output
'''Inserting
True
True
True
Printing
25
15
5'''

題目，一般考察形式：鏈表復(fù)雜操做（leetcode206), 考察鏈表自身性質(zhì)，如環(huán)鏈表。

LC_206

• 邊界條件，鏈表里面只有零或一個(gè)數(shù)，直接返回。

  
  
  遞歸算法

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

#recursive
class Solution(object):
    def reverseLlist(self, head):
        '''
        type head: ListNode
        rtype: ListNode
        '''
        #邊界
        if head is None: return head
        if head.next is None: return head

        #把指向下一個(gè)的節(jié)點(diǎn)取出
        next_node = head.next
        #反轉(zhuǎn)下一個(gè)節(jié)點(diǎn)開始的鏈表
        res = self.reverseLlist(next_node)
        #將頭節(jié)點(diǎn)連回去
        next_node.next = head
        head.next = None
        return res

非遞歸解法

#非遞歸解法
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        #邊界條件
        if head is None: return head
        if head.next is None: return head
        
        #新建空結(jié)果鏈表
        res = None
        while not head is None:
            if res is None: 
                #如果結(jié)果鏈表為空，結(jié)果鏈表等于頭結(jié)點(diǎn)
                res = head
                head = head.next
                res.next = None
            else:
                #如果結(jié)果鏈表不為空
                #先記錄下一個(gè)節(jié)點(diǎn)
                tmp = head.next
                #將當(dāng)前head連到結(jié)果鏈表
                head.next = res
                #更新結(jié)果鏈表頭結(jié)點(diǎn)
                res = head
                #更新head
                head = tmp
            
        return res

#實(shí)例化
node_1 = ListNode(1)
node_2 = ListNode(2)
node_3 = ListNode(3)
node_4 = ListNode(4)
node_1.next = node_2
node_2.next = node_3
node_3.next = node_4
#print(node_3.next)

sol = Solution()
print(sol.reverseLlist(node_1).val)

Leetcode 142 環(huán)形鏈表

• 邊界條件：鏈表為空或一個(gè)數(shù)，直接返回。
• 暴力解法：1.遍歷所有節(jié)點(diǎn)，2.用map儲(chǔ)存訪問過的，3.若遇到訪問過的則鏈表有環(huán)，返回該節(jié)點(diǎn)。-> O(n), 用到額外空間。

• 更好的解法, 問題分析 1. 鏈表是否有環(huán)？2. 環(huán)的入口在哪里？
  怎樣知道有環(huán)，圖中的這個(gè)類比方法和有意思

  
  
  兩個(gè)人不斷在環(huán)中轉(zhuǎn)圈，速度不一樣，最終會(huì)遇上。實(shí)際代碼上設(shè)置兩個(gè)指針，一個(gè)一次跑兩個(gè)格，一個(gè)跑一個(gè)，最后會(huì)取到相同的數(shù)（撞上了）
  
  
  2n是快指針走的步數(shù)
  
  
  從上面得到兩條式子，L是h到s的距離