链表的结构以及相关题目

1. 链表翻转类

a. 206. Reverse Linked List

Reverse a singly linked list. Example: Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

1. 思路 核心步骤：

next = cur.next cur.next = pre pre = cur cur = next

2. 代码

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        pre = None
        cur = head
        while cur:
            _next = cur.next
            cur.next = pre
            pre = cur
            cur = _next
        return pre

b. 92. Reverse Linked List II

Reverse a linked list from position m to n. Do it in one-pass. Note: 1 ≤ m ≤ n ≤ length of list. Example: Input: 1->2->3->4->5->NULL, m = 2, n = 4 Output: 1->4->3->2->5->NULL

1. 思路 a. 创建dummy节点的目的是让边界情况能像非边界情况一样方便处理。（如果m=1，mnode就是第一个节点，此时如果没有dummy节点那么pre节点就为空。 b. 通过设定的i递增找到pre节点，m节点，n节点 c. 找到相应的节点之后就是整个算法的核心：当mnode和nnode没有重合之前，将mnode移到nnode后面，然后令mnode为之前mnode的下一个节点 d. 当mnode和nnode重合时，对应部分的链表就翻转成功了
2. 代码

class Solution(object):
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
        dummy = ListNode(0)
        dummy.next = head
        mnode = head
        nnode = head
        pre = dummy
        i = 1
        while i <= n:
            if i < m:
                mnode = mnode.next
                pre = pre.next
            if i < n:
                nnode = nnode.next
            i += 1
        while(mnode != nnode):
            pre.next = mnode.next
            mnode.next = nnode.next
            nnode.next = mnode
            mnode = pre.next
            mnode = pre.next
        return dummy.next

c. 61. Rotate List

Given a linked list, rotate the list to the right by k places, where k is non-negative. Example 1: Input: 1->2->3->4->5->NULL, k = 2 Output: 4->5->1->2->3->NULL Explanation: rotate 1 steps to the right: 5->1->2->3->4->NULL rotate 2 steps to the right: 4->5->1->2->3->NULL Example 2: Input: 0->1->2->NULL, k = 4 Output: 2->0->1->NULL Explanation: rotate 1 steps to the right: 2->0->1->NULL rotate 2 steps to the right: 1->2->0->NULL rotate 3 steps to the right: 0->1->2->NULL rotate 4 steps to the right: 2->0->1->NULL

1. 思路 a. 题目意思是将尾节点翻转到头结点k（k = 2）次 b. 如果直接按题意将尾节点翻转到头结点的话，每次需要知道该尾节点的pre节点，但是pre节点无法像next节点一样直接获得，所以这时转变一下思路，将“尾节点翻转到头结点k次”转换为“将头结点翻转到尾节点(n - k)次”（n为链表长度）。 c. 将头结点翻转到尾节点的过程：

   head = head.next tail.next = cur tail = cur cur.next = None cur = head

   

2. 代码

class Solution(object):
		def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if not head or not head.next: return head
        n = 1
        tail = head
        while(tail.next):
						tail = tail.next
            n += 1
        print(n)
        cur = head
        for i in range(n - (k % n)):
            head = head.next
            tail.next = cur
            tail = cur
            cur.next = None
            cur = head
        return head

2. 链表找环(Floyd's Tortoise and Hare)

1. 算法 Floyd算法分为两个不同的阶段。第一个阶段是判断在链表中是否有环路，如果不存在就马上返回空，也就不存在第二阶段。第二个阶段就是找到环路的入口。
2. 第一阶段（确定有环） 在这里，我们初始化两个指针-快的fast和慢的slow。接下来，fast和fast从同一个节点出发（head节点），slow每次走一个节点，fast每次走两个节点。如果他们在前进若干步后在同一个节点相遇，我们就返回这个节点，如果最终没有返回节点信息，而是返回空，则代表不存在环路。可以知道只要链表有环，快慢指针终会在某个节点O相遇。
3. 第二阶段（找到环的入口） 第一阶段确定有环了，假设第一阶段slow和fast在O点相遇，非环长部分长度为f，环长为c，换入口距离相遇点距离为a，相遇点距环入口距离为b，设相遇时fast已经走过m圈，slow走过n圈。则此时：

S(slow) = f + m*c + a S(fast) = f + n*c + a S(fast) = 2*S(slow) 则：S(slow) = (n - m)*c（即slow走过的距离为环长的整数倍） 则：f + m*c + a = (n - m)*c 则：f = (n - 2m)*c - a = (n - 2m - 1)*c + c - a = (n - 2m - 1)*c + b 则：f % b = 0

意味着当第一次相遇时，让fast在相遇点不动，slow回到起点，二者每次都只走一步，这样当slow走了f到达环入口时，fast也走了f，而f % b = 0，意味着fast也到达了环入口，此时二者相遇。

a. 141. Linked List Cycle

Given a linked list, determine if it has a cycle in it. To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list. Example 1: Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where tail connects to the second node. Example 2: Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where tail connects to the first node.

代码

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        if not head or not head.next: return False
        record = {}
        cur = head
        while cur:
            if cur in record: return True
            else:
                record[cur] = 1
                cur = cur.next
        return False

b. 142. Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null. To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list. Note: Do not modify the linked list Example 1: Input: head = [3,2,0,-4], pos = 1 Output: tail connects to node index 1 Explanation: There is a cycle in the linked list, where tail connects to the second node. Example 2: Input: head = [1,2], pos = 0 Output: tail connects to node index 0 Explanation: There is a cycle in the linked list, where tail connects to the first node. Example 3: Input: head = [1], pos = -1 Output: no cycle Explanation: There is no cycle in the linked list.

代码

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        def isCycle(head):
            if not head or not head.next: return None
            slow = head
            fast = head
            while fast.next and fast.next.next:
                fast = fast.next.next
                slow = slow.next
                if fast == slow:
                    return fast
            return None
        intersection = isCycle(head)
        if not intersection: return None
        p1 = head
        p2 = intersection
        while(p1 != p2):
            p1 = p1.next
            p2 = p2.next
        return p1