2020.02.10
2020年计划刷 LeetCode 题目 50 道，差不多一周一道题的进度，直到今天，2020年2月10日，我还有刷一道题……
[TOC]
1. LeetCode 21, 83, 141 Easy Linked List
21. Merge Two Sorted List
Difficulty: Easy, Tag: Linked List
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
这个没有任何要点，算练手，不算在这50题里面，所以也就不用多说，直接上代码。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode head = new ListNode(0);
ListNode p = head;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
p.next = l1;
p = p.next;
l1 = l1.next;
} else {
p.next = l2;
p = p.next;
l2 = l2.next;
}
}
if (l1 == null)
p.next = l2;
else
p.next = l1;
return head.next;
}
}
83. Remove Duplicates from Sorted List
Given a sorted linked list, delete all duplicates such that each element appear only once.
Example 1:
Input: 1->1->2
Output: 1->2
Example 2:
Input: 1->1->2->3->3
Output: 1->2->3
这个也没什么好说的，既然是有序的，就遍历链表，和前一个值做对比，相等就删除就可以了。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null)
return head;
int val = head.val;
ListNode p = head;
while (p.next != null) {
if (p.next.val == val)
delete(p.next, p);
else {
p = p.next;
val = p.val;
}
}
return head;
}
private void delete(ListNode node, ListNode pre) {
pre.next = node.next;
}
}
LeetCode 网站给出的解：
public ListNode deleteDuplicates(ListNode head) {
ListNode current = head;
while (current != null && current.next != null) {
if (current.next.val == current.val) {
current.next = current.next.next;
} else {
current = current.next;
}
}
return head;
}
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.
Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
Follow up:
Can you solve it using O(1) (i.e. constant) memory?
第一个思路：利用集合
遍历链表，判断当前结点是否已经存在集合中，存在的话说明有环，否则将结点加入集合。
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* LitNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null)
return false;
Set<ListNode> s = new HashSet<ListNode>();
ListNode p = head;
while (p != null) {
if (s.contains(p))
return true;
s.add(p);
p = p.next;
}
return false;
}
}
时间复杂度：O(1), 空间复杂度: O(n)
方法二：双指针
fast(步长为2) & slow(步长为1)，如果存在环，fast 和 slow 始终不会指向空指针并且 fast 最终会和slow 指向同一个结点。
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* LitNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null)
return false;
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
if (fast == slow)
return true;
slow = slow.next;
fast = fast.next.next;
}
return false;
}
}
