算法(初级):链表

2021年8月12日 17:03 阅读 66 评论 0

1.回文链表

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

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

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

算法分析:

首先我们得明白什么是回文数,回文数就是无论是从左往右,从右往左读都是一个数的数字,如121、1221,,12321等等,那么放到链表里它的概念也是一样的,区别就是每个数字还带了一个指向下一个数字的指针而已。

下面我就说说我对这道题的解法:

回文数都是对称的,我们可以先遍历整个链表,得到链表的长度,这样我们就可以知道这个链表的一半在哪,最最重要的时,在遍历的同时,我们需要将所有的结点全部压栈,作用等会就懂了。

length = 0 # 初始化链表长度为0 
stack = [] # 定义一个空栈 
originHead = head # 保存原本链表的头结点 
while head: 
    length += 1 # 长度+1 
    stack.append(head) # 结点压栈 
    head = head.next # 让结点后移 

经过一次遍历,我们得到了链表的长度并且将链表结点全部压栈,这时候我们就可以得到链表的一半为

middle = length // 2 # 取整数部分 

不管链表长度是奇数还是偶数,我们只需要对它长度的一半向下取整即可,因为如果它是回文链表的话,第middle+1的位置是不影响的,就比如636长度是3,middle是1,第2的位置也就是3,是不影响它成为回文数的。

这时候我们可以开始判断它是不是回文链表了,怎么做呢?

我们都知道,栈是先进后出的,我们将链表压栈再出栈的时候,结点位置是与链表里的位置相反的,我们根据栈的这个性质,可以进行如下操作:

while middle >= 0: 
    node = stack.pop() # 结点出栈 
    # 若与头结点所在的那一半的元素不等于与它对称的元素 
    if node.val != originHead.val:  
        return False 
    originHead = originHead.next # 头结点所在一半的结点后移 
    middle -= 1 

上面我们是通过一个middle次的循环,一一对比头尾对称的两个元素,如果有一对不相等,返回False,循环结束后,返回True。

全部代码:

# Definition for singly-linked list. 
# class ListNode: 
#     def __init__(self, val=0, next=None): 
#         self.val = val 
#         self.next = next 
class Solution: 
    def isPalindrome(self, head: ListNode) -> bool: 
        if not head: 
            return False 
        length = 0 
        stack = [] 
        originHead = head 
        while head: 
            length += 1 
            stack.append(head) 
            head = head.next 
        middle = length // 2 
        while middle >= 0: 
            node = stack.pop() 
            if node.val != originHead.val: 
                return False 
            originHead = originHead.next 
            middle -= 1 
        return True 

利用了栈先进后出的特性,实现了这个算法。

2.环形链表

给定一个链表,判断链表中是否有环。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。 如果链表中存在环,则返回 true。否则,返回 false 。

算法分析:

这是一个很典型的快慢指针的应用场景了,什么是快慢指针呢,举个例子,在操场上跑步的时候,如果一个人跑的很慢,另外一个较快,因为跑道是环形的,所以这两人只要一直在跑步,那么肯定就会相遇,我们根据这个生活常识就可以解答这道题。

直接给出算法:

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

class Solution: 
    def hasCycle(self, head: ListNode) -> bool: 
        # 首先判断链表是否为空或没有下一个结点 
        if not head or not head.next:  
            return False 
        slow = head # 慢指针 
        fast = head # 快指针 
        while fast and fast.next: # 当快指针不为None且有下一个结点 
            slow = slow.next # 慢指针后移 
            fast = fast.next.next # 快指针每次比慢指针多移动一个结点 
            if fast == slow: # 若两指针相遇 
                return True 
        return False   

算法很简单,就是模拟两人跑步,一个快一个慢,判断他俩是否会交会就可以解答这道题了。

如果你对上面的算法有更好的想法,可以在评论区说出你的看法哦~

PS:以上题目均来自LeetCode

最后修改于2021年8月28日 22:39
©允许规范转载

版权声明:如无特殊说明,文章均为本站原创,转载请注明出处

本文链接:https://www.yangyingqi.com/51.html

线性表 Python
微信
支付宝
登录后即可进行评论/回复
文章目录