链表解题

链表相关题_python版

在O(1)时间删除链表结点

题目：给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该结点。

思路：我们要删除结点i，先把i的下一个结点i.next的内容复制到i，然后在把i的指针指向i.next结点的下一个结点即i.next.next，它的效果刚好是把结点i给删除了。需要考虑如果这个节点是链表的尾节点那么就需要从头遍历这个链表了。（通常，在单向链表中，删除一个链表的结点，都会先从表头开始遍历整个链表，找到需要删除的结点的前一个结点，然后将这个结点的(指向下一个结点的)指针元素指向需要删除结点的下一个结点，最后把需要删除的结点删除．但此过程的平均时间复杂度为 O(n)． ）

class ListNode:
    def __init__(self, value):
        self.value = value
        self.next_ = None

def deleteNode(self,pHead,Node):
        if Node == None or pHead == None:
            return
        if Node.next != None: # else情况1：只有一个Node节点；情况2：Node节点在尾巴
            Node.val = Node.next.val
            Node.next = Node.next.next
        elif Node == pHead:# 如果链表只有一个节点，那么就把头节点删掉就好了
            pHead.val = None
        else:
            pNode = pHead  # 把Node节点删除，然后接上一个None
            while pNode.next != Node:
                pNode = pNode.next
            pNode.next = None
        return pHead

合并两个排序的链表(要求不新建链表)

题目：输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。

思路：非递归情况：找到两个链表中头节点值相对更小的链表，将其作为主链表，第二个链表中的元素则不断加入到主链表中。具体策略是：主链表定义两个指针，指向两个相邻的元素。当第二个链表中的元素值小于主链表中第二个指针时，将第二个链表的当前元素插入到主链表两个指针指向的元素中间，并调整指针指向。 不要让链表断开，考虑链表为空的几种情况。

#  ============非递归版本===============
def Merge(self, pHead1, pHead2):
    if not pHead1:
        return pHead2
    if not pHead2:
        return  pHead1
    mainHead = pHead1 if pHead1.val <= pHead2.val else pHead2 # 主链
    secHead = pHead2 if mainHead == pHead1 else pHead1 # 副链
    mergeHead = mainHead
    mainNext = mainHead.next # 主链第二个指针
    while mainNext and secHead: 
        if secHead.val <= mainNext.val: # 副链节点插入到两个指针之间
            mainHead.next = secHead # 第一个指针连接到副链头指针
            secHead = secHead.next # 副链头指针后移
            mainHead.next.next = mainNext # 副链头指针连接到第二个指针
            mainHead = mainHead.next # 第一个指针后移（变成原副链的头指针），插入操作第二个指针不需要后移
        else:
            mainHead = mainNext
            mainNext = mainNext.next
    if not mainNext: # 副链元素都比第二个指针要大，不能插入，要拼接
        mainHead.next = secHead
    return mergeHead
# ==================递归版本=================
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        if pHead1 is None: # 处理末尾状态，pHead1为空，要拼接的就是pHead2了
            return pHead2
        if pHead2 is None:
            return pHead1
        if pHead1.val < pHead2.val:
            pHead1.next = self.Merge(pHead1.next,pHead2)
            return pHead1 # 返回整段拼接后的链表
        else:
            pHead2.next = self.Merge(pHead1,pHead2.next)
            return pHead2

二叉搜索树与双向链表

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

思路：

1. 核心算法依旧是中序遍历
2. 不是从根节点开始，而是从中序遍历得到的第一个节点开始
3. 定义两个辅助节点listHead(链表头节点)、listTail(链表尾节点)。事实上，二叉树只是换了种形式的链表；listHead用于记录链表的头节点，用于最后算法的返回；listTail用于定位当前需要更改指向的节点。了解了listHead和listTail的作用，代码理解起来至少顺畅80%。

过程图示例

'''
稍微多说一句，其实这段代码也就5行，2行是中序遍历的代码；3行是更改节点指向的代码，为if、else行。if语句段只有在中序遍历到第一个节点时调用，自此之后listHead不变，listTail跟随算法的进度。对比中序遍历可以看出来，实际上只是中序遍历中的第八行代码被上述的if-else语句替代了，仅此而已。
'''
class TreeNode:
    def __init__(self, x):
        self.left = None
        self.right = None
        self.val = x

class Solution:
    def __init__(self):
        self.listHead = None
        self.listTail = None
    def Convert(self, pRootOfTree):
        if pRootOfTree==None:
            return
        self.Convert(pRootOfTree.left)
        if self.listHead==None:  # if/else替换中序遍历存储值
            self.listHead = pRootOfTree # if这一段只有中序遍历的第一个节点出现，即最左子树
            self.listTail = pRootOfTree # 此时，链表头尾指针都指向中序第一个节点
        else:
            self.listTail.right = pRootOfTree # 尾指针与中序下一个节点互连，有right属性是因为上一步self.listTail和self.listHead已经指向pRootOfTree了
            pRootOfTree.left = self.listTail
            self.listTail = pRootOfTree # 尾指针指向中序下一个节点
        self.Convert(pRootOfTree.right)
        return self.listHead

翻转部分链表

题目：给定一个单链表的头指针 head， 以及两个整数 a 和 b下标，在单链表中反转 linked_list[a-b] 的结点，然后返回整个链表的头指针 。

思路：采用翻转单链表的思路，回顾一下

'''
翻转单链表
思路很简单：1->2->3->4->5，遍历链表，把1的next置为None，2的next置为1，以此类推，5的next置为4。得到反转链表。
'''
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        if pHead==None or pHead.next==None:
            return pHead
        pre = None # 前指针
        cur = pHead # 当前指针
        while cur!=None:
            tmp = cur.next # 记录下一个指针，为下一步当前指针后移准备
            cur.next = pre
            pre = cur
            cur = tmp
        return pre

# 翻转部分链表
class Solution:
    def reverseBetween(self, head, m, n):
        # 计算需要逆至的节点数
        reverse_length = n - m + 1
        pre_head = None # 初始化要记录的前驱节点
        result = head   # 最终转换后要返回的链表头结点

        # 将head向后移动m-1个位置
        while head and m > 1:
            pre_head = head
            head = head.next
            m -= 1

        # 记录翻转后的链表尾部，翻转后的尾巴即为当前head
        modify_list_tail = head
        pre = None # 前指针

        # 逆置n - m + 1个节点
        while head and reverse_length: #和翻转单链表一样，翻转后和第一、第三段是断开的
            tmp = head.next 
            head.next = pre
            pre = head
            head = tmp
            reverse_length -= 1

        # 此时，尾巴为空， modify_list_tail指向最后一个非空元素
        # 连接逆置后的链表尾与第三段的头结点结合，此时head已经指向第三段正序的头结点
        modify_list_tail.next = head

        # 如果pre_head不为空，说明不是从第一个节点开始逆至，即m>1
        if pre_head is not None:
            # pre_head指向第一段最后一个元素，连接逆序后的头结点
            pre_head.next = pre #pre指向逆序后头结点，head为第三段的头结点
        else:
            # 此时m=1，则逆置后的头结点就是链表的头结点，即翻转整个单链表
            result = pre
        return result

链表插入排序(leetcode 147 Insertion Sort List)

题目：利用插入排序对链表进行排序

思路：1->3->2->4->null，将头结点和后面的部分断开，变成1->null和3->2->4->null，1->null看做是排好序的部分，添加的时候依次取后面的那部分的节点，比如在这里，先取3，然后对前面排好序的链表从前往后遍历，找到应该插入的位置即可。

"""
Definition of ListNode
class ListNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""


class Solution:
    """
    @param: head: The first node of linked list.
    @return: The head of linked list.
    """
    def insertionSortList(self, head):
        # write your code here
        if head is None:
            return None
        if head.next is None:
            return head
        l=ListNode(-1)
        while head:
            node=l # 每次从头开始
            fol=head.next # 保持下一个，防止断开
            while node.next and node.next.val < head.val: # 插入到node和node.next之间
                node = node.next
            head.next = node.next  # 先连接后面head-<node.next
            node.next = head     # 再连接前面
            head = fol
        return l.next

链表归并排序(leetcode 148 Sort List)

题目：要求我们用O(nlogn)算法对链表进行排序

class ListNode(object):
    def __init__(self, val, next=None):
        self.val = val
        self.next = next
 
class Solution:
    # 归并法
    def sortList(self, head):
        # write your code here
        if head is None or head.next is None:
            return head
        pre = head
        slow = head               # 使用快慢指针来确定中点
        fast = head
        while fast and fast.next:
            pre = slow
            slow = slow.next
            fast = fast.next.next
        
        left = head  
        right = pre.next  # 第二段头结点
        pre.next = None           # 从中间打断链表
        left = self.sortList(left)  
        right = self.sortList(right)  
        return self.merge(left,right)
        
    def merge(self, left, right): #合并两个有序链表
        pre = ListNode(-1) # 新链表
        first = pre # 新链表头结点
        while left and right:
            if left.val < right.val:
                pre.next = left
                pre = left
                left = left.next
            else:
                pre.next = right
                pre = right
                right = right.next
        if left:
            pre.next = left
        else:
            pre.next = right             
        return first.next

两两交换链表中相邻的两个元素

题目：交换链表中相邻的两个元素。 注意第一个节点与第二个节点要交换位置，而第二个节点不用与第三个节点交换位置。 如要交换链表中A->B->C->D中的B和C需要做如下操作（交换B和C）：

• 将A指向C
• 将B指向D
• 将C指向B

思路：在头节点之前加一个假节点就可以使所有的交换都符合上面的情况。

class Solution(object):
    def swapPairs(self, head):
        dummy = ListNode(-1)
        dummy.next = head # 假结点连接原链表
        temp = dummy # 头结点
        while temp.next and temp.next.next:
            node1 = temp.next  # node1是B
            node2 = temp.next.next  # node2是C
            temp.next = node2  # A指向C
            node1.next = node2.next  # B指向D
            node2.next = node1  # C指向B
            temp = temp.next.next  # 跳过两个
        return dummy.next

判断两个链表相交和相交的第一个节点

思路1：链表两个链表的长度差diff，然后快指针先走diff步，然后快慢指针一起走。直到两个指针相同，否则无相交节点。（需要先遍历得到两个链表长度）

思路2：两个指针一起走，当一个指针p1走到终点时，说明p1所在的链表比较短，让p1指向另一个链表的头结点开始走，直到p2走到终点，让p2指向短的链表的头结点，那么，接下来两个指针要走的长度就一样了 ，然后就可以一起走，直到两个指针相同。(若无交点，可以一开始在链表尾巴的设置一个标志点)

# 思路二
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
        p1, p2 = pHead1, pHead2
        while p1 != p2:
            p1 = pHead2 if not p1 else p1.next
            p2 = pHead1 if not p2 else p2.next
        return p1

分隔链表

题目：给定一个链表以及一个目标值，把小于该目标值的所有节点都移至链表的前端，大于或等于目标值的节点移至链表的尾端，同时要保持这两部分在原先链表中的相对位置。

思路：两个链表指针，一个负责收集比目标小的，一个收集大于等于目标的。

class Solution(object):
    def partition(self, head, x):
        dummy = ListNode(-1)
        dummy.next = head
        small_dummy = ListNode(-1)
        large_dummy = ListNode(-1)

        # small_prev和large_prev往后遍历增加，small_dummy和large_dummy则负责最后作为返回头结点
        small_prev = small_dummy
        large_prev = large_dummy
        while dummy.next:  # head第一个节点
            curr = dummy.next
            if curr.val < x:
                small_prev.next = curr
                small_prev = small_prev.next
            else:
                large_prev.next = curr
                large_prev = large_prev.next
            dummy = dummy.next

        large_prev.next = None  # 最后指针置为none
        small_prev.next = large_dummy.next  # large_dummy对应的是大链表的第一个数
        return small_dummy.next  # 返回的是small_dummy

重排链表

将单向链表L0→L1→…→Ln-1→Ln转化为L0→Ln→L1→Ln-1→L2→Ln-2→…的形式，也就是从头部取一个节点，从尾部取一个节点，直到将原链表转化成新的链表。

思路：

1. 去中间节点，将链表分为两段.
2. 翻转后一段
3. 拼接

class Solution:
    def reorderList(self, head):
        if not head:
            return
        # split {1,2,3,4,5} to {1,2,3}{4,5}
        fast = slow = head 
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        head1 = head
        head2 = slow.next
        slow.next = None
        # reverse the second {4,5} to {5,4}
        cur, pre = head2, None
        while cur:
            tmp = cur.next # 标记下一个
            cur.next = pre
            pre = cur
            cur = tmp
        # merge
        cur1, cur2 = head1, pre
        while cur2:
            nex1, nex2 = cur1.next, cur2.next
            cur1.next = cur2
            cur2.next = nex1
            cur1, cur2 = nex1, nex2