160. 相交链表
编写一个程序，找到两个单链表相交的起始节点。
如上面的两个链表：
在节点 c1 开始相交。
示例 1：
输出：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 个节点。
留神：
- 如果两个链表没有交点，返回 null.
- 在返回后果后，两个链表仍须放弃原有的构造。
- 可假定整个链表构造中没有循环。
- 程序尽量满足 O(n) 工夫复杂度，且仅用 O(1) 内存。
题解
办法一：
用两个指针别离获取两个链表得长度，失去长度差 n。
长链表的指针从头结点跑 n 步，短链表的指针指向短链表头指针，之后两个指针同步向后跑，直到两个指针相交。
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//1. 计算两个链表的长度之差
ListNode p1 = headA;
ListNode p2 = headB;
int n = 0;
while (p1!=null){
p1 = p1.next;
n++;
}
while (p2!=null){
p2 = p2.next;
n--;
}
//p1 指向长链，p2 指向短链
if (n>0){
p1 = headA;
p2 = headB;
}else {
p1 = headB;
p2 = headA;
}
n = Math.abs(n);
// 长链先走 n 步
for (int i = 0; i<n; i++){p1 = p1.next;}
//p1,p2 一起走
while(p1!=p2){
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
}办法二：
更简洁的办法先使得长链表指针达到离末端的间隔与短链表长度雷同。
p1, p2 别离指向链表 headA 和 headB，若 p1 先跑完，则 p1 指向 headB, 若 p2 跑完，则将 p2 指向 headA，直到 p1 与 p2 雷同。
例如对于链表:A={1,3,5,7,9,11} 和 B={2,4,9,11}，相交于结点 9, 两个链表长度相差为 2. 那么链表 B 少跑两个结点。
指针 p2 在链表 B 先跑完，将 p2 重置向 A, p1,p2 持续同步向后跑，指针 p1 在 A 中会跑完多的两个结点，同时 p2 在 B 中也会同步跑 2 个结点，此时 p2 指向的地位正好是比链表 A 比链表 B 长出的那一部分。最初 p1 指向 headB，p1 和 p2 此时离开端的间隔雷同，只须要同步向后走直到遇到交点。
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p1 = headA;
ListNode p2 = headB;
while (p1!=p2){
p1 = p1==null? headB: p1.next;
p2 = p2==null? headA: p2.next;
}
return p1;
}
}工夫复杂度 O(m+n)
空间复杂度 O(1)
206. 反转链表(简略)
起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
反转一个单链表。
示例:
输出: 1->2->3->4->5->NULL
输入: 5->4->3->2->1->NULL进阶:
你能够迭代或递归地反转链表。你是否用两种办法解决这道题？
解答：
1. 迭代版
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {val = x;}
* }
*/
class Solution {public ListNode reverseList(ListNode head) {
ListNode curr = head;
ListNode prev = null;
ListNode temp = null;
while (curr!=null){
temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}
}工夫复杂度 O(n)
空间复杂度 O(1)
2. 递归版
class Solution {public ListNode reverseList(ListNode head) {if (head==null || head.next==null){return head;}
ListNode res = reverseList(head.next); // 反转链表 head.next
// 最初将 head 反转
head.next.next = head;
head.next = null;
return res;
}
}工夫复杂度 O(n)
空间复杂度 O(n)
- 合并两个有序链表
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输出：1->2->4, 1->3->4
输入：1->1->2->3->4->4题解：相似于归并排序的归并局部
class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode head = new ListNode(-1);
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;
}
}
// 有且仅有一个列表没有遍历完
p.next = l1 == null ? l2 : l1;
return head.next;
}
}工夫复杂度：O(m+n)
空间复杂度：O(1)
83. 删除排序链表中的反复元素（简略）
给定一个排序链表，删除所有反复的元素，使得每个元素只呈现一次。
示例 1:
输出: 1->1->2
输入: 1->2示例 2:
输出: 1->1->2->3->3
输入: 1->2->3题解：
1. 双指针
class Solution {public ListNode deleteDuplicates(ListNode head) {if (head == null || head.next == null){return head;}
ListNode pre = head;
ListNode curr = pre.next;
while (curr != null){if (curr.val != pre.val){
pre.next = curr;
pre = pre.next;
}
curr = curr.next;
}
pre.next = null;
return head;
}
}2. 单指针*
class Solution {public ListNode deleteDuplicates(ListNode head) {
ListNode curr = head;
while (curr !=null && curr.next != null){if (curr.val == curr.next.val){curr.next = curr.next.next; // 若以后结点与下一个节点值相等，跳过两头雷同的结点}else{curr = curr.next; // 否则不跳过}
}
return head;
}
}工夫复杂度 O(n)
空间复杂度 O(1)
19. 删除链表的倒数第 N 个节点 (中等)
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
阐明：给定的 n 保障是无效的。进阶：
你能尝试应用一趟扫描实现吗？
题解：一趟扫描法
应用两个指针，指针 p1 先走 n 步，另一个指针 p2 才从头节点开始同步向后走，此时两个指针距离 n 个指针，当 p1 走到开端时，p2 恰好在倒数第 n + 1 个结点上，删除掉倒数第 n 个结点即可。
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
ListNode curr = head;
while(curr!=null){
curr = curr.next;
if (n != 0){ //curr 先走 n 步
n--;
}else{ //curr 走了 n 步之后，pre 开始走
pre = pre.next;
}
}
pre.next = pre.next.next;
return dummy.next;
}
}工夫复杂度 O(L)，L 示意链表长度
空间复杂度 O(1)
82. 删除排序链表中的反复元素 II
给定一个排序链表，删除所有含有反复数字的节点，只保留原始链表中 没有反复呈现 的数字。
示例 1:
输出: 1->2->3->3->4->4->5
输入: 1->2->5
示例 2:
输出: 1->1->1->2->3
输入: 2->3题解
解法一：尾插不反复的节点
class Solution {public ListNode deleteDuplicates(ListNode head) {ListNode dummy = new ListNode();
ListNode tail = dummy;
// 找不反复的节点，将不反复的节点尾插入 tail 前面
// 用双指针 L, R 记录反复区间 [i,j), 若[i,j) 长度为 1，则 i 为不反复节点，尾插！// 若若 [i,j) 长度不为 1，则 i 是反复节点，不必尾插
for (ListNode L = head, R = head; R != null; L = R){while (R!= null && L.val == R.val){R = R.next;}
if (L.next == R){ // L 的下一个节点就是 R, 那么 L 不是反复元素，尾插
tail.next = L;
tail = L;
tail.next = null;
}
}
return dummy.next;
}
}工夫复杂度：O(n)
空间复杂度：O(1)
解法二：删除反复节点
class Solution {public ListNode deleteDuplicates(ListNode head) {ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy, cur = head;
while (cur != null && cur.next != null) {if (cur.val != cur.next.val) {if (pre.next != cur) pre.next = cur.next;
else pre = pre.next;
}
cur = cur.next;
}
if (pre.next != cur) pre.next = cur.next;
return dummy.next;
}
}工夫复杂度：O(n)
空间复杂度：O(1)
24. 两两替换链表中的节点 (中等)
给定一个链表，两两替换其中相邻的节点，并返回替换后的链表。
你不能只是单纯的扭转节点外部的值，而是须要理论的进行节点替换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.题解：
1. 迭代
class Solution {public ListNode swapPairs(ListNode head) {ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
ListNode curr = dummy.next;
while (curr != null && curr.next != null){
ListNode temp = curr.next;
curr.next = curr.next.next;
temp.next = curr;
pre.next = temp;
pre = curr;
curr = curr.next;
}
return dummy.next;
}
}工夫复杂度 O(n)
空间复杂度 O(1)
2. 递归
// 递归
class Solution {public ListNode swapPairs(ListNode head) {if (head == null || head.next == null){return head;}
ListNode first = head;
ListNode second = head.next;
first.next = swapPairs(second.next); // 第一个结点的下一个结点为第二个结点前面结点替换后的检点
second.next = first; // 第二个结点指向第一个结点
return second; // 当初第二个结点为头结点，因而返回第二个结点
}
}工夫复杂度：O(n)
空间复杂度：O(n)
445. 两数相加 II *（中等）
给定两个非空链表来代表两个非负整数。数字最高位位于链表开始地位。它们的每个节点只存储单个数字。将这两数相加会返回一个新的链表。
你能够假如除了数字 0 之外，这两个数字都不会以零结尾。
进阶:
如果输出链表不能批改该如何解决？换句话说，你不能对列表中的节点进行翻转。
示例:
输出: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输入: 7 -> 8 -> 0 -> 7题解：
1. 借用栈
用两个栈别离寄存两个链表的数值，每次计算对应数位和时，弹出栈顶元素后累加。
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode dummy = new ListNode(0);
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
//l1 入栈
ListNode p = l1;
while (p != null){stack1.push(p.val);
p = p.next;
}
//l2 入栈
p = l2;
while (p != null){stack2.push(p.val);
p = p.next;
}
// 栈顶元素相加
int carry = 0; // 进位
while (!stack1.isEmpty() || !stack2.isEmpty() || carry!=0){
// 两数相加，再加上进数
int sum = 0;
if (!stack1.isEmpty()){sum += stack1.pop();
}
if (!stack2.isEmpty()){sum += stack2.pop();
}
sum += carry;
// 求余数
// 插入新节点
int remainder = sum % 10;
ListNode s = new ListNode(remainder);
s.next = dummy.next;
dummy.next = s;
carry = sum/10; // 下一轮进位
}
return dummy.next;
}
}工夫复杂度 O(n+m)
空间复杂度 O(n+m)
234. 回文链表 *（中等）
起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
请判断一个链表是否为回文链表。
示例 1:
输出: 1->2
输入: false示例 2:
输出: 1->2->2->1
输入: true进阶 ：
你是否用 O(n) 工夫复杂度和 O(1) 空间复杂度解决此题？
解答：
1. 借用栈：
思考到栈构造出栈时是逆序的，因而借助栈。
扫描一遍链表，并将数值寄存到栈中；
再扫描一遍链表，每扫描一个结点查看是否与栈顶元素相等，并弹出一个元素。若每次都相等，则是回文链表。
空间复杂度 O(n)
2. 栈 + 快慢指针：
链表后半段入栈，并将链表前半段与栈比拟。
（找中点的形式，快指针一次走两步，慢指针一次走一步）
空间复杂度 O(n/2)
3. 快慢指针 + 反转链表：
链表后半段逆序，比拟两个链表是否相等。
链表后半段再次还原回来。
留神的中央：
首先不论链表结点个数是奇数个还是偶数个，后局部头结点都是 p1 后一个结点，因而 p1 确定了，后半局部就确定了。
其次当链表结点为奇数个时，那么前半部分链表长度比后半局部多 1，但在比对时，不必思考前半部分最初一个结点，只有后半局部链表指针到了结尾，那么就算比对胜利。
工夫复杂度 O(n+n/2) = O(n);
只用到了常数个指针，因而空间复杂度为 O(1).
JAVA 代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {val = x;}
* }
*/
class Solution {public boolean isPalindrome(ListNode head) {
// 定义一个快指针和一个慢指针
ListNode p1 = head;
ListNode p2 = head;
if (head == null || head.next == null) return true;
// 找到中点，p1 指向中点, p2 指向中点的前面一个结点
while(p2.next!=null && p2.next.next!=null){
p1 = p1.next;
p2 = p2.next.next;
}
p2 = p1.next;
p1.next = null;
// 反转链表后半局部，rev 为反转后的链表
ListNode p3 = null;
while (p2!=null){
ListNode temp = p2.next;
p2.next = p3;
p3 = p2;
p2 = temp;
}
ListNode rev = p3;
// 比拟两个链表
p1 = head;
while(p3!=null){if ( p1.val == p3.val){
p1 = p1.next;
p3 = p3.next;
}
else break;
}
if (p3 == null){return true;}else{return false;}
}
}工夫复杂度 O(n)
空间复杂度 O(1)
725. 分隔链表 *（中等）
给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个间断的局部。
每局部的长度应该尽可能的相等: 任意两局部的长度差距不能超过 1，也就是说可能有些局部为 null。
这 k 个局部应该依照在链表中呈现的程序进行输入，并且排在后面的局部的长度应该大于或等于前面的长度。
返回一个合乎上述规定的链表的列表。
示例 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].
题解：
- 结构新的链表
先求出链表长度n, 则数组中每条链表的长度至多为n/k, 若n%k = rem>0, 则前 rem 个数组长度再加1，为len+1. 构建新链表，将相应长度的节点增加到链表中即可。
class Solution {public ListNode[] splitListToParts(ListNode root, int k) {ListNode[] res = new ListNode[k];
int n = 0;
ListNode curr = root;
while(curr!=null){
curr = curr.next;
n++;
}
int len = n / k;
int rem = n % k; // 前 rem 个链表的长度为 len+1, 其余链表长度为 len
// 数组中增加链表
curr = root;
for (int i = 0; i < k; i++){ListNode dummy = new ListNode(-1);
ListNode p = dummy;
for (int j = 0; j < len + (rem>0?1: 0); j++){ // 每个链表中增加节点
if (curr!=null){p = p.next = new ListNode(curr.val);
curr = curr.next;
}
else p.next = null; // 若原链表分隔完，将空链表放入未退出链表的数组中
}
res[i] = dummy.next;
rem--; // 结构好一条链表，rem 减 1
}
return res;
}
}工夫复杂度 O(n+k)，若 k 比拟大，最多要新加 k - 1 个空节点
空间复杂度 O(max(n+k))
2. 在原链表上分隔
curr 指向以后节点，走了对应长度后断开。
class Solution {public ListNode[] splitListToParts(ListNode root, int k) {ListNode[] res = new ListNode[k];
ListNode curr = root;
int n = 0;
while(curr!=null){
curr = curr.next;
n++;
}
int len = n/k;
int rem = n%k;
curr = root;
for (int i=0; i<k; i++){res[i] = curr;
for(int j =0; j< len + (rem>0?1: 0)-1; j++){if (curr!=null){curr = curr.next;}
}
// 断开
if (curr!=null){
ListNode temp = curr.next;
curr.next = null;
curr = temp;
}
rem--;
}
return res;
}
}工夫复杂度 O(n+k), 若 k 比拟大，最多要新加 k - 1 个空节点
空间复杂度 O(k)
328. 奇偶链表（中等）
起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl…
给定一个单链表，把所有的奇数节点和偶数节点别离排在一起。请留神，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试应用原地算法实现。你的算法的空间复杂度应为 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阐明:
该当放弃奇数节点和偶数节点的绝对程序。
链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。
题解
将奇节点放在一个链表里，偶节点放在另一个链表里。而后把偶链表接在奇链表的尾部。
public class Solution {public ListNode oddEvenList(ListNode head) {if (head == null) return null;
ListNode odd = head;
ListNode even_head = head.next;
ListNode even = even_head;
while (even != null && even.next != null) { // 留神边界条件
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = even_head;
return head;
}
}工夫复杂度 O(n)
空间复杂度 O(1)