首页 > > 网络编程 > 其它 >

数据结构与算法 —— 链表linked list(06)

2018-06-18 02:35:48来源：未知阅读 ()

回文链表

链接

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

进阶：
你能在 O(n) 的时间和 O(1) 的额外空间中做到吗？

解题思路：

回文链表的特点就是对称。

把链表放到栈中去，利用栈的先进后出的规则，和原链表一一做比较。全部相等，则是回文链表。

代码实现如下：

# 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(1):

代码如下：

# 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

环形链表

链接

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

说明：不允许修改给定的链表。

进阶：
你是否可以不用额外空间解决此题？

解题思路：

涉及到环形的数据结构，都可以考虑Floyd算圈问题(又叫龟兔赛跑问题)。

算法描述

（1）求环

初始状态下，假设已知某个起点为节点为节点S。现设两个指针t和h，将它们均指向S。

同时让t和h往前推进，h的速度为t的2倍），直到h无法前进，即到达某个没有后记的节点时，就可以确定从S出发不会遇到环。反之当t与h再次相遇时，就可以确定从S出发一定会进入某个环，设其为环C。（h和t推进的步数差是环长的倍数）

（2）求环的长度

上述算法刚判断出存在环C时，t和h位于同一节点，设其为节点M。仅需令h不动，而t不断推进，最终又会返回节点M，统计这一次t推进的步数，就是环C的长度。

（3）求环的起点

为了求出环C的起点，只要令h仍均位于节点M，而令t返回起点节点S。随后，同时让t和h往前推进，且速度相同。持续该过程直至t与h再一次相遇，此相遇点就是环C的一个起点。

假设出发起点到环起点的距离为m，已经确定有环，环的周长为n，（第一次）相遇点距离环的起点的距离是k。那么当两者相遇时，慢指针（t）移动的总距离i = m + a * n + k，快指针（h）的移动距离为2i，2i = m + b * n + k。其中，a和b分别为t和h在第一次相遇时转过的圈数。让两者相减（快减慢），那么有i = (b - a) * n。即i是圈长度的倍数。

将一个指针移到出发起点S，另一个指针仍呆在相遇节点M处两者同时移动，每次移动一步。当第一个指针前进了m，即到达环起点时，另一个指针距离链表起点为i + m。考虑到i为圈长度的倍数，可以理解为指针从链表起点出发，走到环起点，然后绕环转了几圈，所以第二个指针也必然在环的起点。即两者相遇点就是环的起点。

具体的代码实现：

# 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