Linked List

【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;
    }
}