At the end of the exam, the average score of the class only got the second grade, the teacher in charge then asked: everyone knows the world’s first peak Qomolangma, anyone know the world’s second peak is what? Just as the teacher was going to continue to speak, he heard a voice in the corner: “K2”

preface

2018.11.8 punch in tomorrow’s topic: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

The title

Leetcode141 – Circular Linked List https://leetcode-cn.com/problems/linked-list-cycle/description/ English link https://leetcode.com/problems/linked-list-cycle/description/

Detailed questions

Given a linked list, determine whether there are rings in the list. Advanced: Can you solve this problem without using extra space?

The title,

Train of thought

  • Use two Pointers, one fast and one slow;
  • The fast one takes two steps at a time, the slow one takes one step at a time, and if there’s a loop, the fast one can definitely catch up with the slow one, so they’re equal

code

 1/ * *

 2 * Definition for singly-linked list.

 3 * class ListNode {

 4 *     int val;

 5 *     ListNode next;

 6 *     ListNode(int x) {

 7 *         val = x;

 8 *         next = null;

 9*}

10*}

11* /

12public class Solution {

13    public boolean hasCycle(ListNode head) {

14        if(head == null || head.next == null)

15            return false;

16        ListNode fast = head.next;

17        ListNode slow = head;

18        while(slow ! =null&& fast ! =null)

19        {

20            if(fast == slow)

21                return true;

22            slow = slow.next;

23            if(fast.next ! =null)

24                fast = fast.next.next;

25            else

26                return false;

27        }

28        return false;

29    }

30}

Copy the code

The code on

  • Lines 16-17 define the fast or slow Pointers
  • Lines 20-21 if the fast pointer meets the slow pointer, it indicates that there is a ring;
  • Take two fast steps and one slow step at a time

conclusion

# 2018.11.8 clock

Author Chowgory experienced the autumn admission of 2019. He is a computer master of Harbin Institute of Technology and a Java engineer admitted to Baidu. Welcome to follow my wechat official account: The official account has 3T programming resources, and my friend and I (admitted baidu C++ engineer) prepared nearly 200 MB of required interview Java and C++ experience during the autumn recruitment, and there is a leetcode punch card group and technical exchange group every day, welcome to follow.