链表

链表定义：

是一种递归的数据结构，它或者为空，或者是指向一个node的引用，该结点还有一个元素和指向另一条链表的引用。（结点+指向下一个node的指针）

链表特点：

1. 最后一个节点的next指向null。
2. 与数组不同，不需要new出一块空间，所以不用考虑空间不足和浪费的问题。
3. 需要多少，就会生成多少挂接起来。
   因此，链表具有动态的能力，不需要处理固定容量的问题
   但是，由于动态的能力，确实了高效的随机访问（random access ）的能力。也就是不能像数组一样通过index 来访问对应的元素。链表靠next链接，每个节点的存储地址都不同，我们只能用next来找到自己要找的元素。所以，增删改查操作的复杂度都是O（n）,数组是O（1）

插入node：

insertNode.next = prevNode.next
prevNode.next = insertNode

删除node：

prevNode.next = delNode.next
delNode.next = null

链表相关问题：

反转链表：

输入一个链表，反转链表后，输出链表的表头。

思路：现在的node去指向前一个Node，后面的Node指向前面的Node，知道最后一个Node：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
  def ReverseList(self,pHead):
    pReverseHead = None
    pNode = pHead
    pPrev = None
    while  pNode:
      pNext = pNode.next
      if not pNext:
        pReverseHead = pNode
      pNode.next = pPrev
      pPrev = pNode
      pNode = pNext
    return pReverseHead

链表中环的入口结点：

在一个链表中，若有环，输出环的入口结点，否则输出null。

思路：一个fast指针一次移动两个结点，一个slow指针一次移动一个结点。因为有环所以两个必定相遇。相遇之后，fast从头结点出发变为一次一步，slow和fast会在环入口相遇。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def EntryNodeOfLoop(self, pHead):
        # write code here
        #fast一次走2步，slow一次走一步，如果该链表有环，两个指针必然在环内相遇
        if not pHead or pHead.next == None or pHead.next.next==None:
            return None
        slow = pHead.next
        fast = pHead.next.next
        while slow!= fast:
            if fast.next == None or fast.next.next ==None:
                return None
            slow = slow.next
            fast = fast.next.next
            #此时只需要把其中的一个指针重新指向链表头部，另一个不变（还在环内），
            #这次两个指针一次走一步，相遇的地方就是入口节点。
        fast = pHead
        while slow!=fast:
            slow = slow.next
            fast = fast.next
        return fast

删除链表中的重复结点：

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

思路： 有重复就跳过，对后面的node进行递归去重。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        if pHead ==None or pHead.next==None:
            return pHead
        head = pHead.next
        if head.val!= pHead.val:
            pHead.next = self.deleteDuplication(pHead.next)
        else:
            while pHead.val == head.val and head.next:
                head = head.next
            if head.val != pHead.val:
                pHead = self.deleteDuplication(head)
            else:
                return None
        return pHead

链表中倒数第K个结点：

输入一个链表，输出该链表中倒数第k个结点。

思路：两个指针，P1移动K个结点，所以还剩下N-K个结点，这时候P2从头结点出发，P1到达最后一个结点时候，P2正好也走了N-K个结点，也就是倒数第K个。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        if k<=0 or not head:
            return None
        p1 = head
        p2 = head
        for i in range(k-1):
            if p1.next != None:
                p1=p1.next
            else:
                return None
        while p1.next:
            p1 = p1.next
            p2 = p2.next
        return p2

合并两个排序的链表：

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

思路：递归

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        if pHead1.val<= pHead2.val:
            pMergeHead = pHead1
            pMergeHead.next = self.Merge(pHead1.next,pHead2)
        else:
            pMergeHead = pHead2
            pMergeHead.next = self.Merge(pHead1,pHead2.next)
        return pMergeHead

两个链表的第一个公共结点：

输入两个链表，找出它们的第一个公共结点。

思路：两个链表分别放入栈，每次同时弹出一个，最后一个相同的结点就是第一个公共结点。

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        if not pHead1 or not pHead2:
            return None
        stack1=[]
        stack2=[]
        first = None
        while pHead1:
            stack1.append(pHead1)
            pHead1 = pHead1.next
        while pHead2:
            stack2.append(pHead2)
            pHead2 = pHead2.next
            
        while stack1 and stack2:
            top1 = stack1.pop()
            top2 = stack2.pop()
            if top1 == top2:
                first=top1
            else:
                break
        return first

二叉搜索树与双向链表：

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

思路：二叉搜索树的特点：左结点<根结点<右结点。所以用中序遍历，就可排序。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Convert(self, pRootOfTree):
        # write code here
        if not pRootOfTree:
            return 
        if not pRootOfTree.left and not pRootOfTree.right:
            return pRootOfTree
        #处理左子树
        self.Convert(pRootOfTree.left)
        left = pRootOfTree.left
        #连接根与左子树最大节点
        if left:
            while(left.right):
                left = left.right
            pRootOfTree.left,left.right = left,pRootOfTree
            
        self.Convert(pRootOfTree.right)
        right = pRootOfTree.right
          
        if right:
            while(right.left):
                right = right.left
            pRootOfTree.right,right.left = right,pRootOfTree
        
        while (pRootOfTree.left):
            pRootOfTree = pRootOfTree.left
            
        return pRootOfTree