【1】链表删除
203. Remove Linked List Elements
解法一：遍历删除，需要新建一个dummy node，否则无法return head node
// runtime: 2ms
// worst time = O(n)
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;
}
}
解法二：递归删除（待补充）
237. Delete Node in a Linked List
没有前一个node，无法用前一个指向当前node的后一个。
class Solution {
public void deleteNode(ListNode node) {
if(node!=null && node.next!=null){
node.val=node.next.val;
node.next=node.next.next;
}
}
}
19. Remove Nth Node From End of List
思路：two pointers
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if(head==null) return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode point1 = dummy;
ListNode point2 = dummy;
for(int i=1; i<=n; i++){
point2 = point2.next;
}
while(point2.next!=null){
point1=point1.next;
point2=point2.next;
}
point1.next=point1.next.next;
return dummy.next;
}
}
83. Remove Duplicates from Sorted List
有可能删除head的时候需要dummy.next=head，否则只需要dummy=head就可以了。
注意三个连续重复的现象。
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode cur = head;
while(cur!=null && cur.next!=null){
if(cur.next.val==cur.val) cur.next=cur.next.next;
else cur=cur.next;
}
return head;
}
}
82. Remove Duplicates from Sorted List II
在以cur.val当判别条件时前面要加上cur!=null
同样注意三个连续的情况
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
ListNode cur = head;
while(cur!=null){
if(cur.next!=null && cur.next.val==cur.val){
int val = cur.val;
cur=cur.next;
while(cur!=null && val==cur.val){
cur=cur.next;
}
pre.next=cur;
}else{
cur=cur.next;
pre=pre.next;
}
}
return dummy.next;
}
}
【2】链表反转
206. Reverse Linked List 反转整个链表
解法一：遍历 Time: O(n) Space O(1)
class Solution {
public ListNode reverseList(ListNode head) {
//iterative only once
ListNode newHead = null;
ListNode next;
while(head!=null){
next=head.next;
head.next=newHead;
newHead=head;
head=next;
}
return newHead;
}
}
解法二：递归 Time: O(n) Space: O(n)
class Solution {
public ListNode reverseList(ListNode head) {
return recursiveReverse(head, null);
}
public ListNode recursiveReverse(ListNode head, ListNode newHead){
if(head!=null){
ListNode next=head.next;
head.next=newHead;
return recursiveReverse(next, head);
}
return newHead;
}
}
92. Reverse Linked List II 反转部分链表
思路：一个一个插入pre后面的节点。
class Solution {
//头插法
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy = new ListNode(0);
dummy.next=head;
ListNode pre=dummy;
for(int i=0; i<m-1; i++){
pre=pre.next;
}
ListNode start=pre.next;
for(int i=0; i<n-m; i++){
ListNode cur=start.next;
start.next=cur.next;
cur.next=pre.next;
pre.next=cur;
}
return dummy.next;
}
}
24. Swap Nodes in Pairs 成对交换
class Solution {
//four pointers dummy, pre, head, next
public ListNode swapPairs(ListNode head) {
if(head==null||head.next==null) return head;
ListNode dummy = new ListNode(0);
dummy.next=head;
ListNode newHead=head.next;
ListNode pre=dummy;
while(head!=null && head.next!=null){
ListNode next=head.next;
head.next=next.next;
pre.next=next;
next.next=head;
pre=head;
head=head.next;
}
return newHead;
}
}
25. Reverse Nodes in k-Group 反转每个k节点
141. Linked List Cycle 判断是否有环
思路：快慢指针
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast=head;
ListNode slow=head;
while(fast!=null && fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fast==slow) return true;
}
return false;
}
}
142. Linked List Cycle II 找到环的起始点
需要补的知识点：同余
fast和slow相遇时，slow一定是第一次走环。
第一次相遇时slow走过的距离：a+b，fast走过的距离：a+b+c+b。
fast走的距离是slow的两倍，2(a+b) = a+b+c+b，可以得到a=c
L=b+c=a+b，也就是说，从一开始到二者第一次相遇，循环的次数就等于环的长度。
要找环的起始点：因为a=c，让head和fast一起走，每次走一格，相遇的点就是起始点。
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast=head;
ListNode slow=head;
while(fast!=null && fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fast==slow) break;
}
if(fast==null || fast.next==null) return null;
while(head!=fast){
head=head.next;
fast=fast.next;
}
return head;
}
}
21. Merge Two Sorted Lists
思路：双指针
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 创建一个新链表
ListNode x = new ListNode(0);
ListNode dummy = x;
//当两个链表都不为空时，双指针接入新链表
while(l1!=null && l2!=null){
if(l1.val<=l2.val) {
x.next=l1;
l1=l1.next;
}
else {
x.next=l2;
l2=l2.next;
}
x=x.next;
}
//其中一个为空或两个都为空后，把非空链表的内容接上
if(l1!=null) x.next=l1;
else if(l2!=null) x.next=l2;
return dummy.next;
}
}
【】两数相加
2. Add Two Numbers
思路：不能全都加起来，会溢出，要一位一位加。
注意最后一位的进位不要忘记加上。
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode result=new ListNode(-1);
ListNode dummy=result;
int num=0;
while(l1!=null || l2!=null || num>0){
if(l1!=null){
num+=l1.val;
l1=l1.next;
}
if(l2!=null){
num+=l2.val;
l2=l2.next;
}
ListNode x = new ListNode(num%10);
result.next=x;
result=result.next;
num/=10;
}
return dummy.next;
}
}
445. Add Two Numbers II
思路：用stack
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> stack = new Stack<Integer>();
Stack<Integer> s1 = new Stack<Integer>();
Stack<Integer> s2 = new Stack<Integer>();
while(l1!=null){
s1.push(l1.val);
l1=l1.next;
}
while(l2!=null){
s2.push(l2.val);
l2=l2.next;
}
int sum=0;
while(!s1.isEmpty() || !s2.isEmpty() ||sum!=0){
if(!s1.isEmpty()){
sum+=s1.pop();
}
if(!s2.isEmpty()){
sum+=s2.pop();
}
stack.push(sum%10);
sum/=10;
}
ListNode result = new ListNode(-1);
ListNode dummy=result;
while(!stack.isEmpty()){
ListNode x = new ListNode(stack.pop());
result.next=x;
result=result.next;
}
return dummy.next;
}
}
445. Add Two Numbers II
思路：出一个头出一个尾然后依此规律循环，一开始想到的是后半部分的list可以放进stack中然后pop，但是需要额外的space，参考答案写的是reverse list，时间都是n但是不用额外的space。
class Solution {
public void reorderList(ListNode head) {
if(head==null||head.next==null) return;
//find the middle node (fast and slow points)
ListNode fast = head;
ListNode slow = head;
//slow最后停下的位置总是应该在result的结尾，所以slow应该作为后半部分链表的起始点
//但要反转链表必须知道slow之前的一个node
ListNode temp = null;
while(fast!=null && fast.next!=null){
temp=slow;
slow=slow.next;
fast=fast.next.next;
}
ListNode pre = temp;
//reverse the last half list (insertion from start)
ListNode start = slow;
ListNode cur = start.next;
while(cur!=null){
start.next=cur.next;
cur.next=pre.next;
pre.next=cur;
cur=start.next;
}
//reorder the list
ListNode result = new ListNode(-1);
start=pre.next;
pre.next=null; //cut the first part
while(head!=null){
result.next=head;
head=head.next;
result=result.next;
result.next=start;
start=start.next;
result=result.next;
}
head=result.next;
}
前半部分短，后半部分长，当head==null之后后半部分剩下的不用管，因为也在后面连着。
328. Odd Even Linked List
思路：odd都连成一个链表，even都连成一个，然后两个连起来。
class Solution {
public ListNode oddEvenList(ListNode head) {
if(head==null||head.next==null) return head;
ListNode odd=head, even=head.next;
ListNode evenHead=even;
while(even!=null && even.next!=null){
odd.next=odd.next.next;
even.next=even.next.next;
odd=odd.next;
even=even.next;
}
odd.next=evenHead;
return head;
}
}
725. Split Linked List in Parts
思路：算出root中有多少个node，
class Solution {
public ListNode[] splitListToParts(ListNode root, int k) {
ListNode[] list = new ListNode[k];
if(root==null) return list;
ListNode head=root;
//count the number of node in the root list
int x=0;
while(root!=null){
root=root.next;
x++;
}
//calculate how many node in one list
int mod=x%k, num;
for(int i=0; i<=k-1; i++){
if(i<mod) num=x/k+1;
else num=x/k;
ListNode start=head;
list[i]=start;
if(num==1){
head=start.next;
start.next=null;
}
for(int j=0; j<num-1; j++){
start=start.next;
if(j==num-2) {
head=start.next;
start.next=null;
}
}
}
return list;
}
}
参考答案之后优化
class Solution {
public ListNode[] splitListToParts(ListNode root, int k) {
ListNode[] list = new ListNode[k];
//遍历数组的简便写法！！
int len=0;
for(ListNode head=root; head!=null; head=head.next) len++;
//calculate how many node in one list
int mod=len%k, num=len/k;
ListNode start=null;
for(int i=0; i<k && root!=null; i++, mod--){
list[i]=root;
for(int j=0; j<num+(mod>0?1:0); j++){
start=root;
root=root.next;
}
start.next=null;
}
return list;
}
}
86. Partition List
一开始的思路是：two pointers把小于x的node一个一个进上前面来
class Solution { //1->4->3->2->5->2
public ListNode partition(ListNode head, int x) {
ListNode pre=new ListNode(-1);
ListNode slow=pre, fast=head;
pre.next=fast;
head=pre;
while(fast!=null){
if(fast.val<x && slow.next!=fast){
pre.next=fast.next; //3->5
fast.next=slow.next; //2->4
slow.next=fast; //1->2
//1->2->4->3->5->2
fast=pre.next;
slow=slow.next;
}else{
if(slow.next.val<x) slow=slow.next;
pre=pre.next;
fast=fast.next;
}
}
return head.next;
}
}
改进后：小于x的挂在一个node上，大于x的挂在一个node上，最后再连起来。
class Solution { //1->4->3->2->5->2
public ListNode partition(ListNode head, int x) {
ListNode dummyLess = new ListNode(0);
ListNode dummyMore = new ListNode(0);
ListNode less = dummyLess, more = dummyMore;
while(head!=null){
if(head.val<x){
less.next=head;
less=head;
}else{
more.next=head;
more=head;
}
head=head.next;
}
more.next=null;
less.next=dummyMore.next;
return dummyLess.next;
}
}
138. Copy List with Random Pointer
注意：一定要恢复原始链表（虽然不知道为什么）题目不是说只要deep copy就可以了吗？而且返回的是新的链表。
一开始的想法：但是发现原来的链表无法恢复
后来改成这样：
public class Solution {
public RandomListNode copyRandomList(RandomListNode head) {
if(head==null) return null;
RandomListNode dummy = new RandomListNode(0);
RandomListNode iter=head, next, cur;
//the first step
while(iter!=null){
cur = new RandomListNode(iter.label);
next=iter.next;
iter.next=cur;
cur.next=next;
iter=next;
}
dummy.next=head.next;
//the second step
iter=head;
while (iter != null) {
if (iter.random != null) {
iter.next.random = iter.random.next;
}
iter = iter.next.next;
}
//the third step: restore original and new list's next points
iter=head;
while(iter!=null){
cur=iter.next;
iter.next=cur.next;
//同样注意null情况
if(cur.next!=null) cur.next=cur.next.next;
iter=iter.next;
}
return dummy.next;
}
}
61. Rotate List
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head==null||head.next==null) return head;
ListNode start = head, iter = head, newHead;
//Get the total length
int len;
for(len = 1; iter.next!=null; len++) iter=iter.next;
//如果k是len的整数倍，不用旋转直接返回
if(k % len==0) return start;
//找到切分结点
for(int i=1; i<len - k % len; i++) head=head.next;
newHead=head.next;
head.next=null;
iter.next=start;
return newHead;
}
}
160. Intersection of Two Linked Lists
思路：两个node分别从两个list开始遍历，先到null的返回另一个list的开头，后到null的也返回另一个list的开头，此时两个node举例intersection的距离相同。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode a = headA;
ListNode b = headB;
while(a!=b){
a= a==null ? headB : a.next;
b= b==null ? headA : b.next;
}
return a;
}
}
234. Palindrome Linked List 找回文链表
思路：
1.找到中间元素
2.reverse后半部分
3.前半部分和reverse之后的后半部分对比看是否相等
class Solution {
public boolean isPalindrome(ListNode head) {
if(head==null||head.next==null) return true;
//divide the list into two parts
ListNode mid = middle(head);
//reverse the last half of list
ListNode latter = reverse(mid.next);
while(latter!=null && head.val==latter.val){
head=head.next;
latter=latter.next;
}
if(latter==null) return true;
else return false;
}
}
