课后作业

问题描述

原文链接:142. 环形链表 II

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

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

不允许修改链表。

示例 1:

img

输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

img

输入:head = [1,2], pos = 0
输出:返回索引为 0 的链表节点
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

img

输入:head = [1], pos = -1
输出:返回 null
解释:链表中没有环。

提示:

  • 链表中节点的数目范围在范围 [0, 104]
  • -105 <= Node.val <= 105
  • pos 的值为 -1 或者链表中的一个有效索引

代码实现

Java

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == head){
            return head;
        }
        // 
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                break;
            }
        }
        if(fast == null || fast.next == null){
            return null;
        }
        //统计环的节点个数
        int n = 1;
        while(true){
            fast = fast.next;
            if(fast == slow){
                break;
            }
            n++;
        }
        ListNode pre = head;
        ListNode last = head;
        // last先走n步
        for(int i = 0; i < n; i++){
            last = last.next;
        }
        while(true){
            if(last == pre){
                return pre;
            }
            last = last.next;
            pre = pre.next;
        }
    }
}

Python

# 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
        """
        if(head == None or head.next == head):
            return head
        # 
        fast = head
        slow = head
        while(fast != None and fast.next != None):
            fast = fast.next.next
            slow = slow.next
            if(fast == slow):
                break
        if(fast == None or fast.next == None):
            return None
        #统计环的节点个数
        n = 1
        while(True):
            fast = fast.next
            if(fast == slow):
                break
            n += 1
        pre = head
        last = head
        # last先走n步
        for i in range(n):
            last = last.next
        while(True):
            if(last == pre):
                return pre
            last = last.next
            pre = pre.next

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == NULL || head->next == head){
            return head;
        }
        // 
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL){
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow){
                break;
            }
        }
        if(fast == NULL || fast->next == NULL){
            return NULL;
        }
        //统计环的节点个数
        int n = 1;
        while(true){
            fast = fast->next;
            if(fast == slow){
                break;
            }
            n++;
        }
        ListNode* pre = head;
        ListNode* last = head;
        // last先走n步
        for(int i = 0; i < n; i++){
            last = last->next;
        }
        while(true){
            if(last == pre){
                return pre;
            }
            last = last->next;
            pre = pre->next;
        }
    }
};

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func detectCycle(head *ListNode) *ListNode {
    if head == nil || head.Next == head {
        return head
    }
    // 
    fast := head
    slow := head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            break
        }
    }
    if fast == nil || fast.Next == nil {
        return nil
    }
    //统计环的节点个数
    n := 1
    for {
        fast = fast.Next
        if fast == slow {
            break
        }
        n++
    }
    pre := head
    last := head
    // last先走n步
    for i := 0; i < n; i++ {
        last = last.Next
    }
    for {
        if last == pre {
            return pre
        }
        last = last.Next
        pre = pre.Next
    }
}

发表回复

后才能评论