链表
删除排序链表中的重复元素
给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。
输入:head = [1,1,2]
输出:[1,2]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
|
public ListNode deleteDuplicates(ListNode head) {
ListNode cur = head; while (cur != null && cur.next != null) { if (cur.val == cur.next.val) { cur.next = cur.next.next; } else { cur = cur.next; } }
return head; }
|
合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
|
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null) { return list2; } else if (list2 == null) { return list1; } else if (list1.val < list2.val) { list1.next = mergeTwoLists(list1.next, list2); return list1; } else { list2.next = mergeTwoLists(list1, list2.next); return list2; } }
|
判断链表是否为环形
给你一个链表的头节点 head ,判断链表中是否有环。
输入:head = [3,2,0,-4], pos = 1
输出:true
输入:head = [1,2], pos = 0
输出:true
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
|
public boolean hasCycleMethod1(ListNode head) {
Set<ListNode> set = new HashSet<>();
while (head != null) {
if (!set.add(head)) { return true; }
head = head.next; }
return false; }
public boolean hasCycleMethod2(ListNode head) {
if (head == null || head.next == null) { return false; }
ListNode slow = head; ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) { return false; }
slow = slow.next; fast = fast.next.next; }
return true; }
|
相交链表
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
示例1:
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出:Intersected at ‘8’
解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,6,1,8,4,5]。
在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。
请注意相交节点的值不为 1,因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说,它们在内存中指向两个不同的位置,而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点,B 中第四个节点) 在内存中指向相同的位置。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
|
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode p1 = headA, p2 = headB;
while (p1 != p2) { p1 = p1 == null ? headB : p1.next; p2 = p2 == null ? headA : p2.next; }
return p1; }
|
反转链表
题目:给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
示例 1:
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
示例2:
输入:head = [1,2]
输出:[2,1]
示例3:
输入:head = []
输出:[]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
|
public ListNode reverseList(ListNode head) {
if (head == null) return null;
ListNode pre = null; ListNode now = head;
while (now != null) {
ListNode tmp = now.next;
now.next = pre; pre = now; now = tmp;
} return pre; }
|
回文链表
题目:给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。
示例1:
输入:head = [1,2,2,1]
输出:true
示例2:
输入:head = [1,2]
输出:false
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
|
public boolean isPalindrome(ListNode head) {
List<Integer> list = new ArrayList<>();
ListNode now = head;
while (now != null) { list.add(now.val); now = now.next; }
int front = 0; int end = list.size() - 1;
while (front < end) {
if (!list.get(front).equals(list.get(end))) return false;
front++; end--; }
return true; }
|
设计哈希集合
题目:不使用任何内建的哈希表库设计一个哈希集合(HashSet)。
实现 MyHashSet 类:
void add(key) 向哈希集合中插入值 key 。
bool contains(key) 返回哈希集合中是否存在这个值 key 。
void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值,什么也不做。
示例1:
输入:
[“MyHashSet”, “add”, “add”, “contains”, “contains”, “add”, “contains”, “remove”, “contains”]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
输出:
[null, null, null, true, false, null, true, null, false]
解释:
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1); // set = [1]
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(1); // 返回 True
myHashSet.contains(3); // 返回 False ,(未找到)
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(2); // 返回 True
myHashSet.remove(2); // set = [1]
myHashSet.contains(2); // 返回 False ,(已移除)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
|
private static final int BASE = 769;
private LinkedList[] list;
public Lb_7() { list = new LinkedList[BASE];
for (int i = 0; i < BASE; i++) { list[i] = new LinkedList<Integer>(); }
}
public String print(){ return Arrays.toString(list); }
public void add(int key) {
int m = hash(key);
Iterator<Integer> iterator = list[m].iterator();
while (iterator.hasNext()) { Integer now = iterator.next();
if (now == key) { return; }
}
list[m].offerLast(key);
}
public void remove(int key) {
int m = hash(key);
Iterator<Integer> iterator = list[m].iterator();
while (iterator.hasNext()) { Integer now = iterator.next(); if (now == key) { list[m].remove(now); return; } }
}
public boolean contains(int key) {
int m = hash(key);
Iterator<Integer> iterator = list[m].iterator();
while (iterator.hasNext()) {
Integer now = iterator.next(); if (now == key) { return true; } }
return false; }
private int hash(int key) { return key % BASE; }
|
链表的中间结点
题目:给你单链表的头结点 head ,请你找出并返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。
示例1:
输入:head = [1,2,3,4,5]
输出:[3,4,5]
解释:链表只有一个中间结点,值为 3 。
示例2:
输入:head = [1,2,3,4,5,6]
输出:[4,5,6]
解释:该链表有两个中间结点,值分别为 3 和 4 ,返回第二个结点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
|
public ListNode middleNode1(ListNode head) {
int num = 0; ListNode cur = head; while (cur != null) { num++; cur = cur.next; }
int index = 0; ListNode curr = head;
while (index < num / 2) { index++; curr = curr.next; }
return curr;
}
public ListNode middleNode2(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
return slow;
}
|