Leetcode-ListNode, LinkedList
Leetcode 206. Reverse Linked List. 【Easy】【Green】
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head ==null || head.next==null) return head;
ListNode pre = null;
while(head != null){
ListNode nex = head.next;
head.next = pre;
pre = head;
head = nex;
}
return pre;
}
}
Leetcode 2. Add Two Numbers. 【Medium】
设置ListNode a1和a2，目的是不改变input。设置一个int remain，而int sum是在while循环中设置的。
关键点1：while条件：!(a1==null&&a2==null&&remain==0)。
关键点2：remain=sum/10.
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int remain = 0;
ListNode res = new ListNode(0); ListNode tail = res;
ListNode a1 = l1, a2 = l2;
while(!(a1==null&&a2==null&&remain==0)){
int add1 = a1==null? 0:a1.val;
int add2 = a2==null? 0:a2.val;
int sum = add1+add2+remain;
ListNode newNode = new ListNode(sum%10);
tail.next = newNode;
tail = newNode;
remain=sum/10;
if(a1!=null) a1=a1.next;
if(a2!=null) a2=a2.next;
}
return res.next;
}
}
Leetcode 141. Linked List Cycle. 【Easy】
LinkedList最简单的题。设置slow，fast，while中slow跑一步，fast跑两步，如果撞上了就return true；在while外面return false。
public class Solution {
public boolean hasCycle(ListNode head) {
if(head==null || head.next==null) return false;
ListNode slow = head;
ListNode fast = head.next;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow==fast) return true;
}
return false;
}
}
Leetcode 24. Swap Nodes in Pairs. 【Medium】
题目概要：ListNode 两两交换位置。
设置dummy，ListNode L1和L2，写while循环，条件是L2和L2.next，while内有三步。
【
ListNode L1 = xxx (ListNode),
//若L1 = k1(另外的ListNode), 不会改变 xxx (ListNode)。因为是java值传递，传递了地址。只是把k1的地址存放在L1,替换掉了xxx的地址。
//若l1.next = yyyy，也会改变xxx (ListNode).next。
】
while内代码的原理.jpg
class Solution {
public ListNode swapPairs(ListNode head) {
if(head==null || head.next==null) return head;
ListNode dummy = new ListNode(0);
dummy.next = head; //可以不用写。因为反正会在第一次while中: l1.next = l2.next 改变
ListNode l1 =dummy;
ListNode l2 = head;
while(l2 != null && l2.next != null){
ListNode newStart = l2.next.next; //while内第一步，创建newStart
// l1.next = l2.next;
// l2.next = newStart; while内第二步，改变三个箭头指向。改变是没顺序的，不需要记。把图示画出来就会写这个代码了。
// l1.next.next = l2;
l1.next = l2.next; // 影响了dummy: dummy.next也变成了head.next
l1.next.next = l2;
l2.next = newStart;
l1 = l2; //没影响dummy,只是把l2的地址存放在l1,替换掉了dummy的地址
l2 = newStart; //while内第三步，重新赋值l1和l2
}
return dummy.next;
}
}
Leetcode 328. Odd Even Linked List. 【Medium】
题目概要：先排奇数项后排偶数项。
设置ListNode odd, even, 记录evenStart(这题没有dummy因为)
class Solution {
public ListNode oddEvenList(ListNode head) {
if(head==null || head.next==null) return head;
ListNode odd = head; //把head的地址给odd
ListNode even = head.next;
ListNode evenStart = even;
while(even != null && even.next != null){
odd.next = even.next;
even.next = even.next.next;
odd = odd.next; //把odd.next的地址给odd，不会改变head
even = even.next;
}
odd.next = evenStart;
return head;
}
}
Leetcode 92. Reverse Linked List II. 【Medium】
题目简介：将index从m到n的ListNode，顺序颠倒reverse。
还是需要准确画图，才能写出while循环内的值。这里用了两个for循环，其实相当于两个while+while外面的一个int i。while内的写法不止一种。
运行到中途的交换情况.png
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
ListNode cur = head;
for(int i=1; i<m; i++){
pre = pre.next;
cur = cur.next;
}
for(int i=m; i<n; i++){
// ListNode temp = pre.next; 不止一种写法。达到效果就行。
// pre.next = cur.next;
// cur.next = cur.next.next;
// pre.next.next = temp;
ListNode temp = cur.next;
cur.next = cur.next.next;
temp.next = pre.next;
pre.next = temp;
}
return dummy.next;
}
}
Leetcode 237. Delete Node in a Linked List. 【Easy】
题目简介：删除传入的某个ListNode。
太简单。
class Solution {
public void deleteNode(ListNode node) {
if(node==null) return;
node.val = node.next.val;
node.next = node.next.next;
}
}
Leetcode 19. Remove Nth Node From End of List. 【Medium】
题目简介：删除倒数第n个ListNode。
two-pointer, fast-slow解法。设置ListNode dummy, slow, fast, 令fast先跑n+1步，然后while(),当fast跑到null时，slow刚好跑到倒数n+1步。
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode slow = dummy; //必须这么设置;若设置为head,后面for和while循环容易有bug
ListNode fast = dummy;
// while(n-->=0){
// fast = fast.next;
// }
for(int i=0; i<=n; i++){ //必须是跑n+1次 (从第一个跑到倒数第n个，需要sum-n步;从倒数第n跑到null需要n步)
fast = fast.next; //多跑一步，让slow最后跑到倒数第n+1个的位置
}
while(fast != null){
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
Leetcode 83. Remove Duplicates from Sorted List. 【Easy】
题目简介：排序好的List，删除重复的ListNode.
设置cur，while循环遍历，内部if判断cur.val == cur.next.val.
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head==null || head.next == null) return head;
ListNode cur = head;
while(cur.next != null){
if(cur.val != cur.next.val){
cur = cur.next;
} else {
cur.next = cur.next.next;
}
}
return head;
}
}
Leetcode 203. Remove Linked List Elements. 【Easy】
题目简介：删除等于目标值val的ListNode。
82,83,203思路基本相同。本题，设置dummy，设置cur=dummy，while循环判断cur.next. 【不能if(cur.val==val)】因为这样就没法起到删除的作用(这时要令cur上一个的next=cur.next)。
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head==null) return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode cur = dummy;
while(cur.next != null){
if(cur.next.val == val){
cur.next = cur.next.next;
} else {
cur =cur.next;
}
}
return dummy.next;
}
}
Leetcode 82. Remove Duplicates from Sorted List II. 【Medium】
题目简介：去除重复值的ListNode。
两种方法， 一种是two-pointers, 设置slow-fast，用slow记录不重复的ListNode，fast来记录最后一个重复的ListNode；另一种是只用一个cur记录+int记录重复值，if()判断，若有重复值就用int来记录重复的值，while检测直到最后重复的ListNode。
(1) 设置 two-pointers, slow 和fast。
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head==null||head.next==null) return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode slow = dummy, fast = head;
while(fast!=null){
while(fast.next!=null && fast.val==fast.next.val){
fast=fast.next;
}
if(slow.next==fast){
slow=slow.next;
fast=fast.next;
} else {
slow.next = fast.next;
fast = slow.next; //这里关键。 fast = fast.next;也可。
}
}
return dummy.next;
}
}
//// xx = xxx.next 是不能改变 ListNode的；改变ListNode list的，只能是 xx.next = ...。
(2) ListNode cur + int sameVal 来记录：
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head==null || head.next==null) return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode cur = dummy;
while(cur.next!=null && cur.next.next!=null){
if(cur.next.val==cur.next.next.val){
int sameVal = cur.next.val;
while(cur.next!=null && cur.next.val==sameVal){
cur.next=cur.next.next;
}
} else {
cur=cur.next;
}
}
return dummy.next;
}
}
Leetcode 369. Plus One Linked List. 【Medium】
题目简介：给ListNode 组成的数字 +1.
设置two-pointer, nonNine和nineNode，while循环让nineNode先跑，若不等于9，就赋值给nonNine。跑完后nonNine.val++,并把nonNine后面的数都变成0。return时需要注意：有可能是999的情况，这时返回dummy；否则就是一般情况，返回dummy.next。
关键点1: 让nonNine.val++后，需要让nonNine=nonNine.next。(就是确保nonNine后面所有数字都由9变为0)
class Solution {
public ListNode plusOne(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode nonNine = dummy, nineNode = dummy;
while(nineNode.next!=null){
nineNode = nineNode.next;
if(nineNode.val != 9){
nonNine = nineNode;
}
}
nonNine.val++;
nonNine = nonNine.next;
while(nonNine !=null){
nonNine.val = 0;
nonNine = nonNine.next;
}
if(head.val==0){ //或者判断dummy.val也可以
// dummy.val = 1; nonNine.val++已经达到这个效果了
return dummy;
}
return dummy.next;
}
}
还有把整个List reverse后再处理的方法，但不如上面的方法好。
reverse 的函数可以学一下：
private ListNode reverse(ListNode head){
ListNode prev = null;
while(head != null){
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
Leetcode 66. Plus One.【Easy】
题目简介：给int[ ]组成的数字+1.
倒序遍历整个数组，若发现 != 9, 就++并立即return；若 ==9, 就赋值为0. 遍历完成之后，就肯定是像999的情况(才能遍历完成). 所以，构建新 int[] res并把 res[0]赋值为1。
class Solution {
public int[] plusOne(int[] digits) {
if(digits==null || digits.length==0) return digits;
for(int i=digits.length-1; i>=0; i--){
if(digits[i]!=9){
digits[i]++;
return digits;
} else {
digits[i]=0;
}
}
int[] res = new int[digits.length+1];
res[0] = 1;
return res;
}
}
Leetcode 2. Add Two Numbers. 【Medium】
题目简介：有倒序记录的两个ListNode代表的数字，加法运算。
在while循环中，remain = add1+add2+remain, sum%10放入new ListNode, 然后remain/=10。根据是否把sum(即remain) 写入while条件，分成两个略有区别的写法。若remain没写入while条件，需要在while循环结束后，再判断remain是否>0来确定是否进一位 (即类似两个两位数相加得到三位数的情况)。
把sum(即remain) 写入while条件的写法：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int remain = 0;
ListNode res = new ListNode(0); ListNode tail = res;
ListNode a1 = l1, a2 = l2;
while(!(a1==null&&a2==null&&remain==0)){
int add1 = a1==null? 0:a1.val;
int add2 = a2==null? 0:a2.val;
int sum = add1+add2+remain;
ListNode newNode = new ListNode(sum%10);
tail.next = newNode;
tail = tail.next;
remain=sum/10;
if(a1!=null) a1=a1.next;
if(a2!=null) a2=a2.next;
}
return res.next;
}
没把sum(即remain) 写入while条件的写法：
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
ListNode a1 = l1, a2 = l2;
int sum = 0;
while( !(a1 == null && a2 == null)){
if(a1 != null){
sum += a1.val;
a1 = a1.next;
}
if(a2 != null){
sum += a2.val;
a2 = a2.next;
}
tail.next = new ListNode(sum%10);
tail = tail.next;
sum/= 10;
}
if(sum >0){
tail.next = new ListNode(sum);
}
return dummy.next;
}
Leetcode 160. Intersection of Two Linked Lists. 【Easy】
题目简介：找到两个Linked Lists的交点(ListNode).
计算连个list的长度，让长的list先跑，直到两个list剩余长度相等，然后两个list同时跑，ListNode 相同时就找到了交点。还有一种巧妙方法，时间复杂度是O(m+n).
方法1， Time: O(n) 或者说O(max(m,n)), Space: O(1).
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null) return null;
int countA = 0, countB = 0;
ListNode copyA = headA, copyB = headB;
while(copyA != null){ //也可以把headA和headB传入一个helper方法来计算countA,countB
copyA = copyA.next;
countA++;
}
while(copyB != null){
copyB = copyB.next;
countB++;
}
if(countA<countB){
for(int i=0; i<countB-countA;i++) headB = headB.next;
} else {
for(int i=0; i<countA-countB;i++) headA = headA.next;
}
while(headA != headB){
headA = headA.next;
headB = headB.next;
}
return headA;
}
}
计算list 长度的helper：
private count helper(ListNode head){
int count = 0;
while(head != null){
head = head.next;
count++;
}
return count;
}
方法2，同时遍历list，若走到尽头就从对方的head继续遍历。这样两个list都会把先遍历完自身，然后遍历对方different的那段list，然后在交点相遇。
Time: O(m+n), Space: O(1).
方法2图示
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA==null || headB==null) return null;
ListNode a = headA, b = headB;
while(a != b){
a = a ==null? headB:a.next;
b = b ==null? headA:b.next;
}
return a;
}
Leetcode 21. Merge Two Sorted Lists. 【Easy】
题目简介：合并两个已经排序的lists。
设置dummy，merge，while循环跑完L1/L2，然后判断哪个没跑完就接到merge中。也可用recursive递归方法，代码短，但稍难写。
方法1，Time: O(n), Space: O(1).
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode merge = dummy;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
merge.next = l1;
l1 = l1.next;
} else {
merge.next = l2;
l2 = l2.next;
}
merge = merge.next; //第一次到这里，dummy和merge就脱离了，不再指向同一地址
}
if(l1 !=null){
merge.next = l1;
} else {
merge.next = l2;
}
return dummy.next;
}
}
recursive递归方法。Time: O(n), Space: O(n). //对space的理解还是不够。
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;
}
}
Leetcode 234. Palindrome Linked List.【Easy】
题目简介：判断ListNode组成的list是不是Palindrome(回文)
先创建findMiddle方法找到中间节点middle，然后创建reverse方法，把middle后面的 list 的顺序调转，然后用while循环一一比较 前半段(从head开始) 和 后半段 (从reversedHalf开始).
Time: O(n), Space: O(1).
class Solution {
public boolean isPalindrome(ListNode head) {
if(head==null || head.next==null) return true;
ListNode middle = middle(head);
ListNode reversedHalf = reverse(middle.next); //也可以另外写p=head,q=
while(head != null && reversedHalf != null){
if(head.val != reversedHalf.val) return false;
head = head.next;
reversedHalf = reversedHalf.next;
}
return true;
}
private ListNode middle(ListNode head){ //若是奇数(如5),返回3;若是偶数(如6),返回3; 返回的ListNode是前半段最后一个节点
ListNode slow = head;
ListNode fast = head.next;
while(fast !=null && fast.next !=null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
private ListNode reverse(ListNode head){
ListNode prev = null;
while(head != null){ // head=null时就跳出while循环
ListNode temp = head.next;
head.next = prev;
prev = head;
head = temp;
}
return prev;
}
}
Leetcode 143. Reorder List. 【Medium】
题目简介：把后半段reverse，再间隔插入前半段List
解答过程：先找中点Middle，然后将middle后面的后半段List进行reverse()，最后后半段逐个插入前半段
关键点1: slow = head, fast = head.next; fast是head.next; 而且第一句 if(head==null || head.next==null) return;就是为了fast服务的
关键点2: 用了reverse()后list的后半段都改了；需要用slow.next = null; 来删除后半段
class Solution {
public void reorderList(ListNode head) {
if(head==null || head.next==null) return;
ListNode slow = head, fast = head.next;
//注意slow和fast不同,从而使得返回的slow是前半段的最后一个节点,所以在while之后需要用到slow.next
while(fast != null && fast.next != null){ //跑完while,若为奇数(5返回3),若为偶数(6返回3)
slow = slow.next;
fast = fast.next.next; //可以单独写一个findMiddle函数
}
ListNode reversedHalf = reverse(slow.next);
slow.next = null; //这个特别容易漏掉；reverse()已经把这个list的后半段改变了
while(reversedHalf != null){ //可以单独写一个merge函数
ListNode tempA = head.next;
ListNode tempB = reversedHalf.next;
head.next = reversedHalf;
reversedHalf.next = tempA;
head = tempA;
reversedHalf = tempB;
}
}
private ListNode reverse(ListNode head){
ListNode prev = null;
while(head != null){
ListNode temp = head.next;
head.next = prev;
prev = head;
head = temp;
}
return prev;
}
}
findMiddle 有两种写法，都是为了：3返回2，4返回2，然后用middle.next得到后半段的开始节点
(1)
ListNode slow = head, fast = head.next;
while(fast != null && fast.next != null){
slow =xxx; fast = xxxx;
}
(2)
ListNode slow = head, fast = head;
while(fast.next != null && fast.next.next != null){
slow =xxx; fast = xxxx;
}
Leetcode 142. Linked List Cycle II. 【Medium】
题目简介：找到环的起点。
令slow和fast从head X出发，while循环，若相遇，就令slow2从head X出发，而slow从相遇点Z出发，两者一定会在cycle的起点Y处相遇。需要画图，并数据推导。
这里有数学推导。a是起点到cycle相交点A的距离。b是A到fast与slow相遇点B的距离。c是cycle周长减b剩下的距离。
fast行走距离是slow行走距离的两倍。
有：a+b+(b+c)+N2 = 2 * (a+b+N1)
化简得到 a = N3 + c. (N3为N1和N2之差，即a与c大小相差n圈。)
Leetcode142链表的环形.jpg
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head==null || head.next ==null) return null;
ListNode slow = head, fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(slow == fast){
ListNode slow2 = head; //又有一个slow从起点出发
while(slow!= slow2){
slow = slow.next;
slow2 = slow2.next;
}
return slow;
}
}
return null;
}
}
Leetcode 148. Sort List. 【Medium】
题目简介：在O(nlogn) 时间内和Space O(1)条件下给List排序。
用 merge sort来排序，这题的merge sort和标准代码稍有不同。需要对sortList 进行recursive调用，在sortList中需要getMiddle, 然后recursive两次得到L1和L2： sortList(head), sortList(secondHalf)；然后merge(L1和L2)，需要写merge()方法。
merge sort：
https://www.interviewbit.com/tutorial/merge-sort-algorithm/
https://www.geeksforgeeks.org/merge-sort/
class Solution {
public ListNode sortList(ListNode head) {
if(head==null || head.next==null) return head;
ListNode middle = getMiddle(head);
ListNode secondHalf = middle.next;
middle.next = null;
ListNode l1 = sortList(head);
ListNode l2 = sortList(secondHalf);
return merge(l1,l2);
}
private ListNode getMiddle(ListNode head){
ListNode slow = head, fast = head;
while(fast.next !=null && fast.next.next !=null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
private ListNode merge(ListNode L1,ListNode L2){
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while(L1 !=null && L2 !=null){
if(L1.val < L2.val){
cur.next = L1;
L1 = L1.next;
} else {
cur.next = L2;
L2 = L2.next;
}
cur = cur.next;
}
if(L1 !=null) cur.next = L1;
else cur.next = L2;
return dummy. next;
}
}
Leetcode 25. Reverse Nodes in k-Group. 【Hard】
题目简介：把每隔k个ListNode进行翻转reverse。
Time: O(n). Space: O(1).
while(true)循环，在循环内让tail跑k次，若tail==null跳出循环；然后用newTail记录下一轮的节点的prev。用while循环，在k内进行交换。
关键点1: 若tail==null跳出循环
关键点2: 第二层的while(prev.next!=tail) 循环，很难写。
class Solution {
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 tail = dummy, prev = dummy;
while(true){
int count = 0;
while(count<k && tail!=null){
count++;
tail=tail.next;
}
if (tail==null) break;//最后一轮，不满k的话就不执行reverse
ListNode newTail = prev.next; //例如 1-2-...-8,k=3,newTail依次是1,4,7
while(prev.next!=tail){
ListNode cur=prev.next;//Assign
prev.next=cur.next;//Delete
cur.next=tail.next;
tail.next=cur;//Insert
}
prev=newTail;
tail=newTail;
}
return dummy.next;
}
}
Leetcode 23. Merge k Sorted Lists. 【Hard】
题目简介：把已经排序好的k个List 组成一个排序的List。
用PriorityQueue；实现Comparator功能。
Time: O(nlogk), 因为每次插入和取出，PriorityQueue都是需要 O(logk)的时间。而需要n次插入和取出，所以是O(nlogk)。
Space: O(n); 或者说O(k),k是PriorityQueue所占空间.
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists==null || lists.length==0) return null;
//PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length,(a,b) -> a.val-b.val);
//用上面的Lambda表达式，会更加简便
PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length, new Comparator<ListNode>(){
@Override
public int compare (ListNode l1, ListNode l2) {
if(l1.val == l2.val) {
return 0;
}
return l1.val > l2.val? 1 : -1;
//若是写 >=,是可以,但若插入新数可能会出错，因为数组里就没有相等的概念.所以应该规范地写出return 0的情况
//若是写 return a1.val -a2.val; 可能会导致int越界
}
});
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
for(ListNode list: lists){
if(list !=null)queue.add(list);
}
while(!queue.isEmpty()){
ListNode nex = queue.poll();
cur.next = nex;
cur = cur.next;
if(nex.next !=null) queue.add(nex.next);
// cur.next = queue.poll(); 另一种写法
// cur = cur.next;
// if(cur.next != null) queue.add(cur.next);
}
return dummy.next;
//PriorityQueue 返回优先级高的元素,优先级通过 (a,b) -> a.val-b.val 构建, 若是 b.val-a.val那就是返回最大值了
}
}
