菜单

澳门金沙国际数据结构与算法 —— 链表linked list(06)

2019年5月12日 - 金沙编程资讯

解题思路:

回文链表的表征就是对称。

把链表放到栈中去,利用栈的先进后出的条条框框,和原链表1一做比较。全部万分,则是回文链表。

代码完结如下:

澳门金沙国际 1澳门金沙国际 2

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

class Solution:
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        请注意:python3中的list是有pop的方法的
        """
        stack = []
        cur = head
        while cur:
            stack.append(cur)
            cur = cur.next
        while stack:
            if stack.pop().val != head.val:
                return False
            else:
                head=head.next
        return True

View Code

岁月(O(N)),空间(O(N)),显然不符合。

回文链表

 链接

请检查一个链表是不是为回文链表。

进阶:
你能在 O(n) 的年月和 O(一) 的附加空间中达成呢?

 

环形链表

 链接

给定三个链表,重临链表开端入环的首先个节点。 假若链表无环,则赶回 null

注脚:不允许修改给定的链表。

进阶:
您是或不是能够不用额外空间消除此题?

算法描述

(1)求环

起首状态下,假若已知某些起源为节点为节点S。现设四个指针t和h,将它们均指向S。

而且让t和h往前推动,h的快慢为t的二倍),直到h不可能前进,即达到有个别未有后记的节点时,就能够规定从S启程不会遇见环。反之当t与h再次相遇时,就能够规定从S出发一定会进来有些环,设其为环C。(h和t推进的步数差是环长的倍数)

(贰)求环的长度

上述算法刚决断出存在环C时,t和h位于同1节点,设其为节点M。仅需令h不动,而t不断推进,最终又会回去节点M,计算那二遍t推进的步数,正是环C的长度。

(三)求环的起源

为了求出环C的起源,只要令h仍均位于节点M,而令t重返源点节点S。随后,同时让t和h往前推进,且速度同样。持续该进程直至t与h再1次遇上,此相遇点正是环C的2个源点。

 

比方出发源点到环起源的离开为m,已经规定有环,环的周长为n,(第叁次)相遇点距离环的起源的偏离是k。那么当二者相遇时,慢指针(t)移动的总距离i
= m + a * n + k,快指针(h)的移动距离为二i,2i = m + b * n +
k。在那之中,a和b分别为t和h在率先次相遇时转过的圈数。让相互相减(快减慢),那么有i
= (b – a) * n。即i是圈长度的翻番。

将二个指针移到出发源点S,另叁个指南针仍呆在遭受节点M处两个同时活动,每趟运动一步。当第二个指针前进了m,即达到环起源时,另二个指南针距离链表起源为i
+
m。思虑到i为圈长度的翻番,能够知道为指针从链表源点出发,走到环源点,然后绕环转了几圈,所以第2个指针也决然在环的起源。即两边相遇点正是环的起源。

 

实际的代码完成:

澳门金沙国际 3澳门金沙国际 4

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

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        pre = high = low = head
        if not high or not high.next:
            return None
        while high  and high.next:
            high = high.next.next
            low = low.next
            if high == low:
                break
        if high != None and high == low:
            while high != head:
                high = high.next
                head = head.next
            return high

        return None  

View Code

 

参考:

 

新近的获取:

在做这个题的小时,一时候感觉拿着笔在本上画画,写写,真的比凭空想象要多数,画1画你的笔触,做一下演绎,能让您越来越敞亮。

绝知此事要躬行,说的正是其一意思。希望能和大家齐声多交换,大家相互学习。

 

澳门金沙国际,coding交换群:2267041陆七,愿和各位一齐前行!

微信公众号:

澳门金沙国际 5

解题思路:

论及到环形的数据结构,都能够设想Floyd算圈难题(又叫龟兔赛跑难点)。

进阶:

将链表的后半有的翻转过来,从互相先河相继判断,要是都等于,则为回文链表。这些的时刻是O(N),空间是O(壹):

代码如下:

澳门金沙国际 6澳门金沙国际 7

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
def reveseList(head):
    cur = head
    pre = None
    while cur:
        cur_next = cur.next
        cur.next = pre
        pre = cur
        cur=cur_next
    return pre


class Solution:
    def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        请注意:python3中的list是有pop的方法的
        """
        if not head:
            return True
        fast = slow =head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        slow = slow.next
        slow = reveseList(slow)
        while slow:
            if slow.val != head.val:
                return False
            slow = slow.next
            head = head.next
        return True

View Code

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图