鏈表節點的定義
鏈表作為一種數據結構，由鏈表節點互相連接構成。
鏈表節點包含自身的數據和一個指向下一節點的指針。
"""
Definition of ListNode
"""
class ListNode(object):def __init__(self, val, next=None):self.val = valself.next = next由于節點自身的結構特點，鏈表可以僅由一個頭結點表示。
環形鏈表
顧名思義，環形鏈表指鏈表構建過程中，存在環，即鏈表中某一節點從自身出發，最后可以訪問到自身。
判斷鏈表是否為環形鏈表
- leecode141 LinkedListCycle
這題只需記住，快慢指針。至于中間的判斷條件，再慢慢debug。
class Solution:"""@param head: The first node of linked list.@return: True if it has a cycle, or false"""def hasCycle(self, head):if head is None:return False# 快慢指針，快的走兩步，慢的走一步fast = headslow = headwhile(fast.next and fast.next.next):fast = fast.next.nextslow = slow.nextif fast == slow:return Truereturn False查找環形鏈表的入口
- leetcode142 LinkedListCycleII
在快慢指針的基礎上，如果快慢指針重合，將快慢指針恢復成單步指針x,z，讓x指針從頭開始，z指針從重合位置開始，當x、z指針再次相遇即為環形鏈表的入口Y。這可以通過理論證明，感興趣搜一下。
class Solution(object):def detectCycle(self, head):""":type head: ListNode:rtype: ListNode"""fast = headslow = headwhile(fast.next and fast.next.next):fast = fast.next.nextslow = fast.nextif fast == slow:breakif fast is None:return Nonefast = headwhile(fast != slow):fast = fast.nextslow = slow.nextreturn slow相交鏈表
除了在單獨一條環形鏈表找節點入口，還有一種情況是求解兩條相交鏈表的入口。
- leetcode160 getIntersectionNode
這題理論分析上簡單一點。
假設鏈表1長度（a+c）,鏈表2長度（b+c),姑且a<b；
若同時遍歷，x節點在鏈表1走到尾時，y節點在鏈表2距離尾(b-a)； 這時使走到尾的x節點從鏈表2頭開始，y節點在鏈表2走到尾時，x在鏈表2頭已經走了（b-a)個節點。
此時然y節點在鏈表1頭開始，同時單步移動x、y節點，由于x節點比y節點多走了b-a，下次首次相遇一定是在兩鏈表的交點。
class Solution(object):def getIntersectionNode(self, headA, headB):""":type headA, headB: ListNode:rtype: ListNode"""# 算出長鏈表比短鏈表多的長度，讓長鏈表多走k步if headA is None or headB is None:return NonetmpA = headAtmpB = headBlenA = 0lenB = 0while(tmpA):tmpA = tmpA.nextlenA += 1while(tmpB):tmpB = tmpB.nextlenB += 1if lenA > lenB:for i in range(lenA - lenB):headA = headA.nextelse:for i in range(lenB - lenA):headB = headB.nextwhile(headA != headB):headA = headA.nextheadB = headB.nextreturn headA更多精彩文章，歡迎關注公眾號“Li的白日囈語”。
 又稱為二叉查找樹(Binary Search Tree) - （代碼、分析）)
