链表的题目（无题解，仅供复习）

Reverse LinkedList

方法1:三个指针

    public ListNode reverseList(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode prev = null;
        ListNode curr = head;
        ListNode next;
        
        while(curr != null){
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }

方法2:设置虚拟头结点，然后从头遍历原来的链表，每次都把原链表的节点插入到dummyHead后面。

    public ListNode reverseList(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode dummyHead = new ListNode(-1);
        ListNode curr = head;
        while(curr != null){
            ListNode next = curr.next;
            curr.next = dummyHead.next;
            dummyHead.next = curr;
            curr = next;
        }
        
        return dummyHead.next;
    }

Reverse LinkedList II

方法1：基于上面的三指针法，注意把需要保存的节点都保存一下

    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode prevHead = null;
        int i = 1;
        ListNode curr = head;
        
        while(i<m){
            prevHead = curr;
            curr = curr.next;
            i++;
        }
        ListNode prev = null;
        ListNode next = null;
        
        ListNode reverseTail = curr;
        
        while(i<=n){
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
            i++;
        }
        reverseTail.next = curr;
        
        if(prevHead != null){
            prevHead.next = prev;
            return head;
        }else{
            return prev;    
        }
        
    }

方法2：基于虚拟头结点

    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        int i; 
        //找到反转部分的dummyHead
        for(i = 0; i < m - 1; i ++){
            dummyHead = dummyHead.next;    
        }
        ListNode reverseTail = dummyHead.next;
        ListNode curr = dummyHead.next;
        ListNode next;
        while(i < n){
            next = curr.next;
            curr.next = dummyHead.next;
            dummyHead.next = curr;
            curr = next;
            i++;
        }
        
        reverseTail.next = curr;
        if(reverseTail != head){
            return head;
        }else{
            return dummyHead.next;
        }
    }

Remove Duplicates from Sorted List

    public ListNode deleteDuplicates(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode prev = head;
        ListNode curr = head.next;
        
        while(curr != null){
            if(prev.val == curr.val){
                ListNode delNode = curr;
                prev.next = delNode.next;
                curr = delNode.next;
                delNode.next = null;
            }else{
                prev = curr;
                curr = curr.next;
            }
        }
        
        return head;
    }

Partition List

    public ListNode partition(ListNode head, int x) {
        ListNode lessDummyHead = new ListNode(-1);
        ListNode moreDummyHead = new ListNode(-1);
        
        ListNode curr = head;
        ListNode moreCurr = moreDummyHead;
        ListNode lessCurr = lessDummyHead;
        while(curr != null){
            ListNode next = curr.next;
            
            if(curr.val < x){
                lessCurr.next = curr;
                lessCurr = lessCurr.next;
            }else{
                moreCurr.next = curr;
                moreCurr = moreCurr.next;
            }
            
            curr = next;
        }
        lessCurr.next = moreDummyHead.next;
        moreCurr.next = null;
        
        return lessDummyHead.next;
    }

Odd Even Linked List

    public ListNode oddEvenList(ListNode head) {
        ListNode oddDummyHead = new ListNode(-1);
        ListNode evenDummyHead = new ListNode(-1);
        
        ListNode evenCurr = evenDummyHead;
        ListNode curr = head;
        int i = 1;
        while(curr != null){
            ListNode next = curr.next;
            if((i & 1) == 1){
                oddDummyHead.next = curr;
                oddDummyHead = oddDummyHead.next;
            }else{
                evenCurr.next = curr;
                evenCurr = evenCurr.next;
            }
            curr = curr.next;
            i++;
        }
        
        oddDummyHead.next = evenDummyHead.next;
        evenCurr.next = null;
        
        return head;
    }

Add Two Numbers

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode curr1 = l1;
        ListNode curr2 = l2;
        ListNode newHead = new ListNode(0);
        
        ListNode curr =newHead;
        int carry = 0;
        while(curr1!= null || curr2 != null){
            int x = curr1!=null?curr1.val:0;
            int y = curr2!=null?curr2.val:0;
            int sum = x + y + carry;
            carry =sum/10;
            curr.next = new ListNode(sum%10);
            
            curr = curr.next;
            if(curr1 != null)curr1 = curr1.next;
            if(curr2 != null)curr2 = curr2.next;
        }

        
        if(carry == 1){
            curr.next =new ListNode(1);
        }
        return newHead.next;
    }

Add Two NumbersII

这题可以不停手动reverse，但是用栈更美观一些感觉....

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        
        ListNode curr1 = l1;
        ListNode curr2 = l2;
        
        while(curr1 != null){
            s1.push(curr1.val);
            curr1 = curr1.next;
        }
        
        while(curr2 != null){
            s2.push(curr2.val);
            curr2 = curr2.next;
        }
        
        ListNode dummyHead = new ListNode(0);
        int carry = 0;
        ListNode curr = dummyHead;
        Stack<Integer> s = new Stack<>();
        while((!s1.isEmpty()) || (!s2.isEmpty())){
            int x = s1.isEmpty()?0:s1.pop();
            int y = s2.isEmpty()?0:s2.pop();
            int sum = x + y + carry;
            
            carry = sum/10;
            s.push(sum%10);
        }
        
        if(carry == 1){
            s.push(1);
        }
        while(!s.isEmpty()){
            curr.next = new ListNode(s.pop());
            curr = curr.next;
        }
        
        
        return dummyHead.next;
              
    }

Remove Linked List Elements

设置虚拟头结点，这是链表中的常用的技巧，否则如果第一个节点满足条件，不使用dummyHead，那将需要对头结点特殊处理。

    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode prev = dummyHead;
        while(prev!=null){
            ListNode curr = prev.next;
            if(curr!=null && curr.val == val){
                prev.next = curr.next;
                curr.next = null;
            }else{
                prev = prev.next;
            }
        }
        
        return dummyHead.next;
    }

Remove Dumplicates from Sorted List

    public ListNode deleteDuplicates(ListNode head) {
        if(head == null){
            return null;
        }
        
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        
        ListNode prev = dummyHead;
        ListNode curr = head;
        
        while(curr != null){
            ListNode next = curr.next;
            if(next != null && next.val == curr.val){
                while(next != null && next.val == curr.val){
                    ListNode delNode = next;
                    curr.next = delNode.next;
                    next = next.next;
                    delNode.next = null;
                }
                prev.next = next;
            }else{
                prev = curr;
            }
            
            curr = next;
        }
        
        return dummyHead.next;
    }

Swap Nodes In Pairs

    public ListNode swapPairs(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode p = dummyHead;
        while(p != null && p.next != null){
            ListNode node1 = p.next;
            if(node1.next == null){
                break;
            }
            ListNode node2 = node1.next;
            
            ListNode next = node2.next;
            
            node2.next = node1;
            node1.next = next;
            p.next = node2;
            p = node1;
        }
        
        return dummyHead.next;
    }

Insertion Sort List

    public ListNode insertionSortList(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        
        ListNode originNode = head.next;
        //把链表分割成两部分
        head.next = null;
        
        while(originNode != null){
            
            ListNode prevSorted = dummyHead;
            ListNode newNode = originNode;
            
            while(prevSorted.next != null && prevSorted.next.val <= newNode.val){
                prevSorted = prevSorted.next;
            }
            
            originNode = originNode.next;
            newNode.next = prevSorted.next;
            prevSorted.next = newNode;
        }
        
        return dummyHead.next;
    }

Remove Nth Node From End Of List

快慢指针法去找倒数第N个节点

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode fast = dummyHead;
        ListNode slow = dummyHead;
        for(int i = 0; i < n; i ++){
            fast = fast.next;
        }
        
        while(fast.next!=null){
            fast = fast.next;
            slow = slow.next;
        }
        
        ListNode delNode = slow.next;
        slow.next = delNode.next;
        delNode.next = null;
        return dummyHead.next;
    }

Rotate List

这个题画几个图就能明白题意，其实就是把倒数K个旋转一下，挪到前头去，但是需要注意的问题是，K有可能大于节点数，所以先遍历一遍，因为k可能大于链表节点数，所以遍历一次拿到节点总数，再用k去求余。然后可以直接循环length - k%length次拿到倒数第K+1个节点，然后进行相关的更改指向的操作就可以了。

    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || head.next == null || k == 0){
            return head;
        }    
        
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        
        ListNode p = dummyHead;
        int length = 0;
        
        while(p.next!=null){
            p = p.next;
            length ++;
        }
        
        if(k%length == 0){
            return head;
        }
        
        ListNode tail = p;
        
        p = dummyHead;
        
        for(int i = 0; i < length - k%length; i++){
            p=p.next;
        }
        ListNode newHead = p.next;
        p.next = null;
        
        tail.next = dummyHead.next;
        dummyHead.next = newHead;
        return dummyHead.next;
    }

还有 143 和 148 234

Middle of the Linked List

快慢指针法去找中间节点，还是加上dummyHead更好理解一些。慢的一次走一步，快的一次走两步，那么快的走过的路就是慢的的两倍。奇数和偶数个节点有不同的返回情况，画个图分析一下就可以了。

    public ListNode middleNode(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode fast = dummyHead;
        ListNode slow = dummyHead;
        while(fast != null && fast.next!=null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        if(fast == null){
            return slow;
        }
        return slow.next;
    }