206. 反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-linked-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

迭代法

代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = null;
        while(head != null){
          	ListNode tmp = head.next;
          	head.next = newHead;
          	newHead = head;
          	head = tmp;
        }
        return newHead;
    }

时间复杂度 ：O（N）

空间复杂度 ：O（1）

141. 环形链表

给定一个链表，判断链表中是否有环。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

示例 1：

输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/linked-list-cycle 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

一，快慢指针

此类题目使用快慢指针思想，慢指针一次循环走一步，快指针一次循环走两步，循环到快指针的next为空，两个指针不相遇，则代表没有环，若相遇则有环。

代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null) return false;
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null){
            if (slow == fast) return true;
            slow = slow.next;
            fast = fast.next.next;
        }
        return false;
    }

时间复杂度 ：O（N）

空间复杂度 ：O（1）

二，哈希表

初始化一个set用来存储已经遍历过的node节点的引用（或者内存地址）。

遍历链表，当set中包含node节点时，说明有环，return true。

遍历结束，一直不包含时，说明没环，return false；

代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null) return false;
        Set set = new HashSet();
        while (head != null){
            
            if (set.contains(head)) return true;
            
            set.add(head);
            head = head.next;
        }
        
        return false;
    }

时间复杂度 ：O（N）

空间复杂度 ：O（N）