算法刷题之七链表

算法刷题之七链表

链表

题目:

  1. 链表删除某一个节点
  2. 删除倒数第N个节点
  3. 链表逆序
  4. 回文链表
  5. 判断链表是否有环路
  6. 找出环路链表的入口
  7. 链表排序
  8. 相交链表
  9. 两个连表生成相加链表

链表的数据格式就是如下:
算法刷题之七链表

需要注意的是:链表尾部的next为None。所以判断链表结束时,这是遍历一个链表最常用的结束方式。使用的代码:

while p != None:
    p = p.next

算法刷题之七链表

其实是当p已经指向了next区域,这时next为空,所以能够退出

当使用p.next != None时,这时p指向的最有一个节点,而不是节点的next。

while p.next != None:
    p = p.next

算法刷题之七链表

链表删除某一个节点:

删除节点两种方式:

  1. 当前节点指向下下个节点
    算法刷题之七链表

  2. 将下一个节点赋值给当前节点,然后删除下一个节点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val,node.next.val = node.next.val,node.val
        node.next = node.next.next

删除倒数第N个节点

有两种方式:

  1. 算出倒数N的正数num,然后移动到该节点前一个,删除节点
  2. 设置双指针,指针的间距是倒数N。当快指针到链尾时,慢指针当好到待删除的前一个。
  3. 删除节点需要考虑节点为头结点的情况。这时指针指向头结点,不易删除。解决办法是给头结点增加一个前行节点。将指针指向该前行节点。
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        
        # 设置头结点
        re = ListNode(-1)

        re.next = head
        
        slow = re
        fast = slow
        while n + 1> 0:
            fast =  fast.next
            n -= 1

        while fast != None:
            fast = fast.next
            slow = slow.next

        slow.next = slow.next.next
        return re.next

链表逆序

使用双指针可以将链表逆序。
算法刷题之七链表

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre = None
        cur = head
        while cur:
            temp = cur.next   # 先把原来cur.next位置存起来
            cur.next = pre
            pre = cur
            cur = temp
        return pre

需要注意结束条件。当cur == None时,pre刚好在链尾的位置。返回pre就是返回了新的链表

回文链表

请判断一个链表是否为回文链表。

示例 1:

输入: 1->2
输出: false
示例 2:

输入: 1->2->2->1
输出: true
进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnv1oc/

回文最常用的判断方式是:

  1. 逆序,然后比较逆序之后和逆序之前是否相同。如果相同就是回文,不同就不是回文
  2. 将前一半保存,逆序或者入栈,和后一半比较。如果都相同则是回文。

链表回文有多种方式:

  1. 将链表中所有数据保存到列表中,使用列表的逆序来判断
  2. 利用快慢指针,前一半链表的值入栈,然后出栈和后一半比较判断
  3. 利用快慢指针,逆序前一半链表,和后一半比较
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head or not head.next:
            return True
 
        slow = head
        fast = head
        mystack = []

        while fast and fast.next:
           mystack.append(slow.val)
           fast = fast.next.next
           slow = slow.next
        
        # 奇数状态,需要跨过中间的元素
        if fast:
            slow = slow.next
        
        while slow and slow.val == mystack.pop():
            slow = slow.next

判断链表是否有环路

判断链表是否有环路有两个解决方法,
第一:快慢指针,如果存在环路,快指针一定会追上慢指针
第二:字典。将遍历过的节点存入到字典中,每次遍历时在字典中查找,如果存在则表明有环路。



class Node():

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



node1 = Node(100)
node2 = Node(200)
node3 = Node(300)
node4 = Node(300)
node5 = Node(200)
node6 = Node(100)

node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
node5.next = node6
node6.next = node1


def cycle_link(head):

    fast = head
    slow = head

    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
        if fast == slow:
            return True  
    return False

res = cycle_link(node1)
print(res)
class Solution:
    def hasCycle(self, head: ListNode) -> bool:

        if not head:
            return False
        
        Hash = {}
        temp = head
        while temp != None:
            if Hash.get(temp):
                return True
            else:
                Hash[temp] = True
            temp = temp.next
        return False

找出环路链表的入口

通过计算可以知道,快指针走的距离是慢指针距离的两倍,同时快指针比慢指针多走了一个圆的距离。所以在快慢指针相遇的地方,两个指针以相同的数据在走下去,相遇的地方就是环的入口

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:

        first = head
        second = head

        while first and first.next:
            first = first.next.next
            second = second.next
            if first == second:
                first = head
                while True:
                    if first == second:
                        return first
                    first = first.next
                    second = second.next
                    
        
        return None

链表排序

使用链表这样数据结构实现排序,归并排序的实现如下:
先分开,后合并

def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next: 
            return head
        slow = head
        fast = head
        # 用快慢指针分成两部分
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        # 找到左右部分, 把左部分最后置空
        mid = slow.next
        slow.next = None
        # 递归下去
        left = self.sortList(head)
        right = self.sortList(mid)
        # 合并
        return self.merge(left, right)

    def merge(self, left, right):
        dummy = ListNode(0)
        p = dummy
        l = left
        r = right

        while l and r:
            if l.val < r.val:
                p.next = l
                l = l.next
                p = p.next
            else:
                p.next = r
                r = r.next
                p = p.next
        if l:
            p.next = l
        if r:
            p.next = r
        return dummy.next

相交链表

编写一个程序,找到两个单链表相交的起始节点。
算法刷题之七链表
在节点 c1 开始相交。
原理:两个链表是否有相交的地方,可以通过如下方法测试出来:
走完A之后,从B起始点开始走,同样,走完B之后,从A开始走,这样如果有相交的位置,那么A和B到相交的位置就刚好一致。

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:

        if not(headA and headB):
            return None
        nodea = headA
        nodeb = headB

        while nodea != nodeb:
            
            if nodea is None:
                nodea = headB
            else:
                nodea = nodea.next

            if nodeb is None:
                nodeb = headA
            else:
                nodeb = nodeb.next

        return nodea

两两交换链表中的节点

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
算法刷题之七链表

输入:head = [1,2,3,4]
输出:[2,1,4,3]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
       
        pre_head = ListNode(-1)
        pre_head.next = head
       
        pre_h = pre_head
        p = head

        while p and p.next:
            next_p = p.next
            p.next = next_p.next
            pre_h.next = next_p
            next_p.next = p

            pre_h = p
            p = p.next

        return pre_head.next

两个连表生成相加链表

假设链表中每一个节点的值都在 0 - 9 之间,那么链表整体就可以代表一个整数。
给定两个这种链表,请生成代表两个整数相加值的结果链表。
例如:链表 1 为 9->3->7,链表 2 为 6->3,最后生成新的结果链表为 1->0->0->0。

class Solution:
    def addInList(self , head1 , head2 ):
        def reverse_fun(head):
            pre = None
            p = head
            while p:
                temp = p.next
                p.next = pre 
                pre = p 
                p = temp 
            return pre 
        re_head1 = reverse_fun(head1)
        re_head2 = reverse_fun(head2)
        d = ListNode(0)
        p = d 
        c = 0
        while re_head1 or re_head2 or c:
            if re_head1:
                c += re_head1.val
                re_head1 = re_head1.next
            if re_head2:
                c += re_head2.val
                re_head2 = re_head2.next
            p.next = ListNode(c % 10)
            p = p.next
            c = c // 10
        return reverse_fun(d.next)

链表解题总结

链表是我喜欢的数据结构,因为链表没有太多复杂操作。通常是遍历链表一直到尾节点,然后一边遍历一边配合指针操作。在链表中有几个小技巧可以好好总结一下:

  1. 使用快慢指针可以找到链表的中间位置。
    一个指针是快指针,每次走两步,一个指针是慢指针,每次走一步。当快指针到末尾时,慢指针刚好在链表的中间位置。使用场景:回文链表,归并排序
while first and first.next:
    first = first.next.next
    second = second.next
  1. 带头结点的指针更好操作。在函数中,创建一个带头结点指针更方便操作。
    node = ListNode(None)
    使用场景:删除节点,翻转节点

  2. 链表取奇偶很简单,next的next就能保证奇偶

上一篇:CodeGo.net>如何获取图像中的对象周围的矩形?


下一篇:线段树+扫描线 NAIPC 2019 Intersecting Rectangles