共计 6520 个字符,预计需要花费 17 分钟才能阅读完成。
160. 相交链表
编写一个程序,找到两个单链表相交的起始节点。
如下面的两个链表:
<img src=”https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_statement.png” alt=”img” style=”zoom:50%;” />
在节点 c1 开始相交。
示例 1:
<img src=”https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_example_1.png” alt=”img” style=”zoom:50%;” />
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出:Reference of the node with value = 8
输入解释:相交节点的值为 8(注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。
示例 2:
<img src=”https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_example_2.png” alt=”img” style=”zoom:50%;” />
输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出:Reference of the node with value = 2
输入解释:相交节点的值为 2(注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。
示例 3:
<img src=”https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/14/160_example_3.png” alt=”img” style=”zoom:50%;” />
输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出:null
输入解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。解释:这两个链表不相交,因此返回 null。
注意:
- 如果两个链表没有交点,返回
null
. - 在返回结果后,两个链表仍须保持原有的结构。
- 可假定整个链表结构中没有循环。
- 程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。
设置快慢指针
public ListNode getIntersectionNode (ListNode headA, ListNode headB) {if (headA == null || headB == null) return null;
ListNode p1 = headA;
ListNode p2 = headB;
while (p1 != p2) {if (p1 == null) p1 = headB;
else p1 = p1.next;
if (p2 == null) p2 = headA;
else p2 = p2.next;
}
return p1;
}
206. 反转链表
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
递归法:
public ListNode reverseList(ListNode head) {if(head == null || head.next == null){return head;}
ListNode rest = head.next;
ListNode newHead = reverseList(rest);
rest.next = head;
head.next = null;
return newHead;
}
迭代法:
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode cur = head;
while(cur != null){
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
}
21. 合并两个有序链表
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
双指针思想
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val < l2.val){l1.next = mergeTwoLists(l1.next,l2);
return l1;
}else{l2.next = mergeTwoLists(l1,l2.next);
return l2;
}
}
83. 删除排序链表中的重复元素
给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2
示例 2:
输入: 1->1->2->3->3
输出: 1->2->3
一次遍历,注意边界条件。
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;
}
19. 删除链表的倒数第 N 个节点
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的。
进阶:
你能尝试使用一趟扫描实现吗?
设置哑节点 1,让它走 n+1 步,再设置哑节点 2,然后哑节点 1 和哑节点 2 一起移动,直到哑节点 1 走完链表,此时哑节点 1 和哑节点 2 之间正好隔着 n 个节点,再通过哑节点 2 删除倒数第 n 个节点。
public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = dummy;
for (int i = 1; i <= n + 1;i++){first = first.next;}
ListNode second = dummy;
while(first != null){
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}
234. 回文链表
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?
设置快慢指针,移动速度分别是 2 和 1。当快指针到达链表尾部的时候,慢指针就在正中间(奇数个节点的情况下)或者正中间的左边(偶数个节点的情况下),再将慢指针向后移动一位,反转以慢指针为头的链表,再逐个节点对比是否相等。
public boolean isPalindrome (ListNode head) {if (head == null || head.next == null) return true;
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
slow = slow.next;
slow = reverse(slow);
while (slow != null) {if (head.val == slow.val) {
head = head.next;
slow = slow.next;
} else
return false;
}
return true;
}
private ListNode reverse (ListNode head) {
ListNode newHead = null;
while (head != null) {
ListNode nextNode = head.next;
head.next = newHead;
newHead = head;
head = nextNode;
}
return newHead;
}
24. 两两交换链表中的节点
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
设置哑节点,注意循环条件,指针移动的速度是 2(因为需要两两交换节点)。
public ListNode swapPairs (ListNode head) {ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
while (pre.next != null && pre.next.next != null) {
ListNode l1 = pre.next;
ListNode l2 = pre.next.next;
l1.next = l2.next;
l2.next = l1;
pre.next = l2;
pre = l1;
}
return dummy.next;
}
445. 两数相加 II
给定两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外,这两个数字都不会以零开头。
进阶:
如果输入链表不能修改该如何处理?换句话说,你不能对列表中的节点进行翻转。
示例:
输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7
既然不能改变链表的结构(翻转链表),那就用一个栈来保存链表中的值,可以做到逆向输出。
相加部分的代码逻辑就按常规思路写。
public ListNode addTwoNumbers (ListNode l1, ListNode l2) {Stack<Integer> l1Stack = listNodetoStack(l1);
Stack<Integer> l2Stack = listNodetoStack(l2);
int carry = 0;
ListNode head = new ListNode(-1);
while (!l1Stack.isEmpty() || !l2Stack.isEmpty() || carry != 0) {int x = l1Stack.isEmpty() ? 0 : l1Stack.pop();
int y = l2Stack.isEmpty() ? 0 : l2Stack.pop();
int sum = x + y + carry;
ListNode node = new ListNode(sum % 10);
carry = sum / 10;
node.next = head.next;
head.next = node;
}
return head.next;
}
private Stack<Integer> listNodetoStack (ListNode head) {Stack<Integer> stack = new Stack<>();
while (head != null) {stack.push(head.val);
head = head.next;
}
return stack;
}
725. 分隔链表
给定一个头结点为 root
的链表, 编写一个函数以将链表分隔为 k
个连续的部分。
每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1,也就是说可能有些部分为 null。
这 k 个部分应该按照在链表中出现的顺序进行输出,并且排在前面的部分的长度应该大于或等于后面的长度。
返回一个符合上述规则的链表的列表。
举例:1->2->3->4, k = 5 // 5 结果 [[1], [2], [3], [4], null ]
示例 1:
输入:
root = [1, 2, 3], k = 5
输出: [[1],[2],[3],[],[]]
解释:
输入输出各部分都应该是链表,而不是数组。例如, 输入的结点 root 的 val= 1, root.next.val = 2, \root.next.next.val = 3, 且 root.next.next.next = null。第一个输出 output[0] 是 output[0].val = 1, output[0].next = null。最后一个元素 output[4] 为 null, 它代表了最后一个部分为空链表。
示例 2:
输入:
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
输出: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
解释:
输入被分成了几个连续的部分,并且每部分的长度相差不超过 1. 前面部分的长度大于等于后面部分的长度。
提示:
-
root
的长度范围:[0, 1000]
. - 输入的每个节点的大小范围:
[0, 999]
. -
k
的取值范围:[1, 50]
.
先统计出链表长度,除以 k, 求商和余数,其中:
- 余数代表最后结果中有多少个长链表
- 商代表每个短链表的长度(结果集中后部的链表)
- 长链表比短链表多一个节点
public ListNode[] splitListToParts (ListNode root, int k) {
ListNode cur = root;
int len = 0;
while (cur != null) {
cur = cur.next;
len++;
}
int mod = len % k;
int size = len / k;
cur = root;
ListNode[] ans = new ListNode[k];
for (int i = 0; cur != null && i < k; i++) {ans[i] = cur;
int curSize = size + (mod-- > 0 ? 1 : 0);
for (int j = 0; j < curSize - 1; j++) {cur = cur.next;}
ListNode next = cur.next;
cur.next = null;
cur = next;
}
return ans;
}
328. 奇偶链表
给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1),时间复杂度应为 O(nodes),nodes 为节点总数。
示例 1:
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
示例 2:
输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL
说明:
- 应当保持奇数节点和偶数节点的相对顺序。
- 链表的第一个节点视为奇数节点,第二个节点视为偶数节点,以此类推。
设置三个指针,其中奇指针和偶指针是很自然能想到的,evenHead
起辅助作用,用于将奇链表和偶链表结合起来。
public ListNode oddEvenList (ListNode head) {
ListNode odd = head;
ListNode even = head.next;
ListNode evenHead = even;
while (even != null && even.next != null) {
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = evenHead;
return head;
}