目录
- Reverse BST
- Add Number
- Remove
- Sort
- 148 Sort List
- 147 Insertion Sort List
- 143 Reorder List
- Merge
- Cycle
- Others
A LinkedList Definition
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
题目详解
#206 Reverse Linked List
-
Sol1: 递归 recursion
Sol1.1 从前往后
help函数参数为cur要处理的list，pre为已处理过的list
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null){
return head;
}
return help(head, null);
}
public ListNode help(ListNode cur, ListNode pre){
if(cur.next == null){
cur.next = pre;
return cur;
}
ListNode n = cur.next;
cur.next = pre;
return help(n, cur);
}
Sol1.2 从后往前
先循环找到最后面的Node，开始处理依次翻转整个链表。处理返回翻转后的子链表
public ListNode help2(ListNode cur){
if(cur.next == null){
return cur;
}
ListNode nex = cur.next;
ListNode res = help2(cur.next);
nex.next = cur;
cur.next = null;
return res;
}
-
Sol2: 非递归
Sol2.1 通过stack的方式
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null){
return head;
}
Stack<ListNode> a = new Stack<>();
while(head.next != null){
a.push(head);
head = head.next;
}
ListNode reverse = new ListNode(head.val);
ListNode res = reverse;
while(!a.isEmpty()) {
reverse.next = a.pop();
reverse = reverse.next;
}
reverse.next = null;
return res;
}
Sol2.2 通过迭代iteration的方式
三个指针来做循环，前中后，每次改变cur指针next指向，然后移动三个指针到下一个节点
ListNode prev = null;
ListNode cur = head;
while(cur!=null){
ListNode next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
#92 Reverse Linked List II
Reverse a linked list from position m to n. Do it in one-pass.
- sol1: 指针
public ListNode reverseBetween(ListNode head, int m, int n) {
if(head == null || head.next == null){return head;}
if(n == 1){return head;}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode A = dummy;
ListNode B = dummy.next;
int copy_m = m;
while(m!=1){
A = A.next;
B = B.next;
m--;
}
//ListNode C = B.next;
while(copy_m != n){
if(B.next == null){break;}
ListNode tmp = B.next.next;
B.next.next = A.next;
A.next = B.next;
B.next = tmp;
copy_m++;
}
return dummy.next;
}
- Sol2: 非递归--stack的方式
public ListNode reverseBetween(ListNode head, int m, int n) {
if(head == null || head.next == null || m >= n){return head;}
ListNode dummy = new ListNode(0);
dummy.next = head;
head = dummy;
ListNode pre = head;
for(int i = 1; i < m; i++){
pre = pre.next;
}
ListNode tmp = pre.next;
Stack<ListNode> s = new Stack<>();
int i = 0;
while(m+i <= n){
s.push(tmp);
tmp = tmp.next;
i++;
}
ListNode post = tmp;
ListNode rev = s.pop();
tmp = rev;
while(!s.isEmpty()){
tmp.next = s.pop();
tmp = tmp.next;
}
pre.next = rev;
tmp.next = post;
return dummy.next;
}
#24 Swap Nodes in Pairs
交换链表中相邻的两个元素。
-
sol
交换A-B-C-D中的B和C需要做如下操作：
将A指向C
将B指向D
将C指向B
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode tmp = dummy; //tmp==>A
while(tmp.next!=null && tmp.next.next!=null){
ListNode B = tmp.next;
ListNode C = tmp.next.next;
tmp.next = C;
B.next = C.next;
C.next = B;
tmp = tmp.next.next;
}
return dummy.next;
}
#25 Reverse Nodes in k-Group
将一个链表中每k个数进行翻转，末尾不足k个的数不做变化。
A->B->C->D->E，现在我们要翻转BCD三个节点。进行以下几步：
1.C->B
2.D->C
3.B->E
4.A->D
5.返回及节点B
public ListNode reverseKGroup(ListNode head, int k) {
if(head == null || head.next == null || k < 2) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
ListNode cur = dummy.next;
ListNode end = cur;
int count = 0;
while(end != null){
end = end.next;
count++;
if(count % k == 0){
while(cur.next!=end){
ListNode tmp = cur.next.next;
cur.next.next = pre.next; //c-b
pre.next = cur.next;
cur.next = tmp;
}
pre = cur;
cur = cur.next;
}
}
return dummy.next;
}
#61 Rotate List
将一个链表中的元素向右旋转k个位置。
-
sol
先要用一个count变量求出链表的长度。而k%count就是循环右移的步数。
public ListNode rotateRight(ListNode head, int k) {
if(head == null || k == 0) return head;
ListNode p = head;
int count = 1;
while(p.next!=null){
p = p.next;
count++;
}
k = k % count;
if(k==0){return head;}
ListNode fast = head;
ListNode slow = head;
while(k!=0){
fast = fast.next;
k--;
}
while(fast.next!=null){
slow = slow.next;
fast = fast.next;
}
p.next = head;
head = slow.next;
slow.next = null;
return head;
}
#86 Partition List
给定一个链表以及一个目标值，把小于该目标值的所有节点都移至链表的前端，大于或等于目标值的节点移至链表的尾端，同时要保持这两部分在原先链表中的相对位置。
-
sol 两个指针
一个负责收集比目标小的，一个收集大于等于目标的。
public ListNode partition(ListNode head, int x) {
if(head == null || head.next == null){return head;}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode smallDummy = new ListNode(0);;
ListNode largeDummy = new ListNode(0);;
ListNode smallCur = smallDummy;
ListNode largeCur = largeDummy;
while(dummy.next!=null){
ListNode p = dummy.next;
if(p.val >= x){
largeCur.next = p;
largeCur = largeCur.next;
}else{
smallCur.next = p;
smallCur = smallCur.next;
}
dummy = dummy.next;
}
smallCur.next = largeDummy.next;
largeCur.next = null;
return smallDummy.next;
}
#328 Odd Even Linked List
奇数位置组合在一起，偶数位置的组合在一起。O(1)空间复杂度，O(n)时间复杂度
- sol 链表指针处理
public ListNode oddEvenList(ListNode head) {
if(head == null || head.next == null){return head;}
ListNode odd = head;
ListNode even = head.next;
while(even != null && even.next != null){
ListNode tmp = even.next;
even.next = tmp.next;
tmp.next = odd.next;
odd.next = tmp;
odd = tmp;
even = even.next;
}
return head;
}
#725 Split Linked List in Parts
-
Sol Split Input List
there are N / k items in each part, plus the first N % k parts have an extra item. We can count N with a simple loop.
public ListNode[] splitListToParts(ListNode root, int k) {
ListNode p = root;
int count = 0;
while(p != null){
p = p.next;
count++;
}
int team = count / k; //3
int left = count % k; //1
ListNode[] res = new ListNode[k];
for(int i = 0; i < k; i++){
res[i] = root;
for(int j = 0; j < team-1 && root!=null; j++){
root = root.next;
}
if(left > 0 && root != null && team > 0){
root = root.next;
left--;
}
if(root != null){
ListNode recode = root.next;
root.next = null;
root = recode;
}
}
return res;
}
#2 Add Two Numbers
给定两个链表分别代表两个非负整数。数位以倒序存储，并且每一个节点包含一位数字。将两个数字相加并以链表形式返回
-
Sol1
遍历两个链表，依次相加，把进位的数字计入下一组相加的数字中。
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carry = 0;
ListNode res = new ListNode(0);
ListNode tmp = res;
while(l1!=null&&l2!=null){
int sum = l1.val+l2.val;
int node = carry + sum;
carry = 0;
if(node>9){
carry++;
}
res.next = new ListNode(node%10);
res = res.next;
l1 = l1.next;
l2 = l2.next;
}
while (l1 != null) {
int sum = carry + l1.val;
res.next = new ListNode(sum % 10);
carry = sum / 10;
l1 = l1.next;
res = res.next;
}
while (l2 != null) {
int sum = carry + l2.val;
res.next = new ListNode(sum % 10);
carry = sum / 10;
l2 = l2.next;
res = res.next;
}
if (carry != 0) {
res.next = new ListNode(carry);
}
return tmp.next;
// int sum = getNum(l1) + getNum(l2);
// return getList(sum);
}
- Sol2 递归
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if(l1 == null || l2 == null){return l1 == null? l2 : l1;}
int value = l1.val + l2.val;
ListNode res = new ListNode(value%10);
res.next = addTwoNumbers(l1.next, l2.next);
if(value >= 10){
res.next = addTwoNumbers(new ListNode(value/10), res.next);
}
return res;
#445 Add Two Numbers II
- Sol 栈转存
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> s1 = new Stack<>();
Stack<Integer> s2 = new Stack<>();
while(l1 != null){
s1.add(l1.val);
l1 = l1.next;
}
while(l2 != null){
s2.add(l2.val);
l2 = l2.next;
}
int carry = 0;
ListNode res = new ListNode(0);
while(!s1.isEmpty() || !s2.isEmpty()){
int value = carry;
if(!s1.isEmpty()) value += s1.pop();
if(!s2.isEmpty()) value += s2.pop();
// int value = s1.pop() + s2.pop() + carry;
ListNode tmp = new ListNode(value % 10);
tmp.next = res.next;
res.next = tmp;
carry = value / 10;
}
if(carry != 0){
ListNode tmp = new ListNode(carry);
tmp.next = res.next;
res.next = tmp;
}
return res.next;
}
#19 Remove Nth Node From End of List
删除链表中倒数第n个节点
-
Sol 双指针
加入虚假头节点dummy，使用双指针fast，slow。fast从dummy开始先移动n位。然后fast与slow同时移动，直到fast.next==null，此时slow.next为要删除的节点
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode res = new ListNode(0);
res.next = head;
ListNode slow = res;
ListNode fast = res;
if(head == null) {
return null;
}
if(head.next == null && n==1){
return null;
}
while(n != 0){
n--;
fast = fast.next;
}
while(fast.next!=null){
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return res.next;
}
#203 Remove Linked List Elements
删除链表中制定元素
- Sol 加入虚假头节点dummy
public ListNode removeElements(ListNode head, int val) {
ListNode res = new ListNode(0);
res.next = head;
ListNode cur = res;
while(cur.next != null){
if(cur.next.val == val){
cur.next = cur.next.next;
}else{
cur = cur.next;
}
}
return res.next;
}
#237 Delete Node in a Linked List
just for fun吧～～
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
#83 Remove Duplicates from Sorted List
删除一个有序链表中重复的元素，使得每个元素只出现一次。
- Sol 比较当前节点有后一个节点
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null){return head;}
ListNode p = head;
while(p.next != null){
if(p.val == p.next.val){
p.next = p.next.next;
}else{
p = p.next;
}
}
return head;
}
#82 Remove Duplicates from Sorted List II
把一个有序链表中所有重复的数字全部删光，删除后不再有原先重复的那些数字。
- Sol 加入虚假头节点dummy
public ListNode deleteDuplicates(ListNode head) {
ListNode res = new ListNode(0);
res.next = head;
ListNode cur = res;
ListNode fast = res.next;
while(cur.next != null){
while(fast.next!=null && fast.next.val == cur.next.val){
fast = fast.next;
}
if(cur.next == fast){ //没有重复，两个都进一位
cur = cur.next;
fast = fast.next;
}else{
cur.next = fast.next;
fast = fast.next;
}
}
return res.next;
}
#148 Sort List
Sort a linked list in O(n log n) time using constant space complexity.
由于链表在归并操作时并不需要像数组的归并操作那样分配一个临时数组空间，所以这样就是常数空间复杂度了
- Sol 归并排序+快慢指针
public ListNode sortList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode slow = head;
ListNode fast = head;
while(fast.next!=null && fast.next.next != null){
fast = fast.next.next;
slow = slow.next;
}
ListNode head1 = head;
ListNode head2 = slow.next;
slow.next = null;
head1 = sortList(head1);
head2 = sortList(head2);
head = merge(head1,head2);
return head;
}
private ListNode merge(ListNode a, ListNode b){
ListNode dummy = new ListNode(0);
ListNode p = dummy;
while(a!=null && b != null){
if(a.val <= b.val){
p.next = a;
a = a.next;
}else{
p.next = b;
b = b.next;
}
p = p.next;
}
if(a==null){
p.next = b;
}
if(b == null){
p.next = a;
}
return dummy.next;
}
#147 Insertion Sort List
-
Sol 插入排序
链表只能从前往后比较
public ListNode insertionSortList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode p = head.next;
ListNode q = head;
while(p!=null){
if(p.val >= q.val){
q = p;
p = p.next;
}else{
ListNode p_next = p.next;
ListNode tmp = dummy.next;
ListNode pre_tmp = dummy;
while(tmp.val < p.val && tmp != q){
tmp = tmp.next;
pre_tmp = pre_tmp.next;
}
pre_tmp.next = p;
p.next = tmp;
q.next = p_next;
p = p_next;
}
}
return dummy.next;
}
#143 Reorder List
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
-
Sol 快慢指针+翻转链表+链接链表
去中间节点，将链表分为两段.
翻转后一段
拼接
public void reorderList(ListNode head) {
if(head == null || head.next == null){
return;
}
ListNode slow = head;
ListNode fast = head;
while(fast.next!=null && fast.next.next!=null){
fast = fast.next.next;
slow = slow.next;
}
fast = slow.next;
slow.next = null;
//reverse
ListNode cur = null;
while(fast!=null){
ListNode next = fast.next;
fast.next = cur;
cur = fast;
fast = next;
}
slow = head;
while(slow!=null && cur!=null){
ListNode tmp = cur.next;
cur.next = slow.next;
slow.next = cur;
slow = slow.next.next;
cur = tmp;
}
}
#21 Merge 2 Sorted Lists
修改链表的指针
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 = l2;
p = l2;
l2 = l2.next;
}else{
p.next = l1;
p = l1;
l1 = l1.next;
}
}
if(l1 == null){
p.next = l2;
}else{
p.next = l1;
}
return head.next;
}
#23 Merge k Sorted Lists
将k个排序好的链表合并成新的有序链表
- sol 最小堆--优先队列
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length==0){return null;}
PriorityQueue<Integer> q = new PriorityQueue();
for(ListNode n: lists){
while(n!=null){
q.add(n.val);
n = n.next;
}
}
ListNode dummy = new ListNode(0);
ListNode p = dummy;
while(!q.isEmpty()){
p.next = new ListNode(q.poll());
p = p.next;
}
return dummy.next;
}
#160 Intersection of Two Linked Lists
- sol1 长度
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int l1 = getLength(headA);
int l2 = getLength(headB);
while(l1 < l2){
headB = headB.next;
l2--;
}
while(l1 > l2){
headA = headA.next;
l1--;
}
while(headA != headB){
headA = headA.next;
headB = headB.next;
}
return headA == headB? headA: null;
}
public int getLength(ListNode a){
int count = 0;
while(a != null){
count++;
a = a.next;
}
return count;
}
- sol2 HashSet
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
Set<ListNode> s = new HashSet<>();
while(headA!=null){
s.add(headA);
headA = headA.next;
}
while(headB!=null){
if(s.contains(headB)){
return headB;
}else{
headB = headB.next;
}
}
return null;
}
- sol3 循环
ListNode a = headA;
ListNode b = headB;
while(a != b){
a = a == null ? headA : a.next;
b = b == null ? headB : b.next;
}
return a;
sol1,sol3,sol2
#141 Linked List Cycle
判断一个链表中是否存在着一个环，能否在不申请额外空间的前提下完成
- sol 快慢指针
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while(fast !=null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){return true;}
}
return false;
}
#142 Linked List Cycle II
如果给定的单向链表中存在环，则返回环起始的位置，否则返回为空。最好不要申请额外的空间。
-
sol 快慢指针
因为快指针的速度是慢指针的两倍，所以在相同时间内，它走过的路程是慢指针的两倍。快慢指针在C处相遇，头指针到环起点位置的距离与，C到B的距离相等。
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){break;}
}
if(fast == null || fast.next == null){return null;}
slow = head;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return fast;
}
#234 Palindrome Linked List
-
sol1 Creat a new reversed list
The time and space are O(n).
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null){return true;}
ListNode copyReverse = reverse(head);
while(head != null){
if(head.val != copyReverse.val){return false;}
head = head.next;
copyReverse = copyReverse.next;
}
return true;
}
public ListNode reverse(ListNode head){
ListNode prev = new ListNode(head.val);
ListNode cur = head;
while(cur.next!=null){
ListNode next = new ListNode(cur.next.val);
next.next = prev;
prev = next;
cur = cur.next;
}
return prev;
}
-
sol2 Break and reverse second half
The time is O(n) and space is O(1).
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null){return true;}
ListNode slow = head, fast = head;
while(fast.next != null && fast.next.next!=null){
slow = slow.next;
fast = fast.next.next;
}
fast = slow.next;
slow.next = null;
ListNode pre = null;
ListNode cur = fast;
while(cur != null){
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
slow = head;
while(pre != null){
if(slow.val != pre.val){return false;}
slow = slow.next;
pre =pre.next;
}
return true;
}
总结
- 链表头会发生变化，引入dummy头指针辅助
- 交换链表指针时，注意指针变换
- 快慢指针用于找中间节点，发现环路等
