目錄
- 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函數(shù)參數(shù)為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 從后往前
先循環(huán)找到最后面的Node翰萨，開始處理依次翻轉(zhuǎn)整個鏈表泽腮。處理返回翻轉(zhuǎn)后的子鏈表
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的方式
三個指針來做循環(huán)集索，前中后慧妄，每次改變cur指針next指向肪康，然后移動三個指針到下一個節(jié)點
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個數(shù)進(jìn)行翻轉(zhuǎn)哩牍，末尾不足k個的數(shù)不做變化。
A->B->C->D->E碑宴，現(xiàn)在我們要翻轉(zhuǎn)BCD三個節(jié)點软啼。進(jìn)行以下幾步：
1.C->B
2.D->C
3.B->E
4.A->D
5.返回及節(jié)點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
將一個鏈表中的元素向右旋轉(zhuǎn)k個位置桑谍。
-
sol
先要用一個count變量求出鏈表的長度延柠。而k%count就是循環(huán)右移的步數(shù)。
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
給定一個鏈表以及一個目標(biāo)值锣披，把小于該目標(biāo)值的所有節(jié)點都移至鏈表的前端贞间，大于或等于目標(biāo)值的節(jié)點移至鏈表的尾端，同時要保持這兩部分在原先鏈表中的相對位置雹仿。
-
sol 兩個指針
一個負(fù)責(zé)收集比目標(biāo)小的增热，一個收集大于等于目標(biāo)的。
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
奇數(shù)位置組合在一起胧辽，偶數(shù)位置的組合在一起峻仇。O(1)空間復(fù)雜度，O(n)時間復(fù)雜度
- 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
給定兩個鏈表分別代表兩個非負(fù)整數(shù)邑商。數(shù)位以倒序存儲摄咆，并且每一個節(jié)點包含一位數(shù)字。將兩個數(shù)字相加并以鏈表形式返回
-
Sol1
遍歷兩個鏈表人断，依次相加吭从，把進(jìn)位的數(shù)字計入下一組相加的數(shù)字中。
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 棧轉(zhuǎn)存
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
刪除鏈表中倒數(shù)第n個節(jié)點
-
Sol 雙指針
加入虛假頭節(jié)點dummy恶迈，使用雙指針fast涩金，slow。fast從dummy開始先移動n位暇仲。然后fast與slow同時移動步做，直到fast.next==null，此時slow.next為要刪除的節(jié)點
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 加入虛假頭節(jié)點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
刪除一個有序鏈表中重復(fù)的元素奈附，使得每個元素只出現(xiàn)一次全度。
- Sol 比較當(dāng)前節(jié)點有后一個節(jié)點
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
把一個有序鏈表中所有重復(fù)的數(shù)字全部刪光，刪除后不再有原先重復(fù)的那些數(shù)字桅狠。
- Sol 加入虛假頭節(jié)點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){ //沒有重復(fù)讼载，兩個都進(jìn)一位
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.
由于鏈表在歸并操作時并不需要像數(shù)組的歸并操作那樣分配一個臨時數(shù)組空間轿秧，所以這樣就是常數(shù)空間復(fù)雜度了
- 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 快慢指針+翻轉(zhuǎn)鏈表+鏈接鏈表
去中間節(jié)點，將鏈表分為兩段.
翻轉(zhuǎn)后一段
拼接
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 最小堆--優(yōu)先隊列
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 循環(huán)
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
判斷一個鏈表中是否存在著一個環(huán)咨堤，能否在不申請額外空間的前提下完成
- 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
如果給定的單向鏈表中存在環(huán)菇篡，則返回環(huán)起始的位置，否則返回為空一喘。最好不要申請額外的空間驱还。
-
sol 快慢指針
因為快指針的速度是慢指針的兩倍，所以在相同時間內(nèi)凸克，它走過的路程是慢指針的兩倍议蟆。快慢指針在C處相遇萎战，頭指針到環(huán)起點位置的距離與咐容，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;
}
總結(jié)
- 鏈表頭會發(fā)生變化蚂维，引入dummy頭指針輔助
- 交換鏈表指針時戳粒，注意指針變換
- 快慢指針用于找中間節(jié)點，發(fā)現(xiàn)環(huán)路等
