合并2个有序链表

class Solution {
    public ListNode merge(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode node = head;
        while(l1 != null && l2 != null) {
            if(l1.val<=l2.val){
                node.next = l1;
                l1=l1.next;
            }else{
                node.next=l2;
                l2=l2.next;
            }
                node=node.next;
                node.next=null;
        }
        if(l1 != null)
            node.next=l1;
        if(l2 != null)
            node.next=l2;
        return head.next;
    }
}

合并k个有序链表

class Solution {
    
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length==0)
            return null;
        return recurMerge(lists,0,lists.length-1);
    }
    
    public ListNode recurMerge(ListNode[] lists, int left, int right) {
        if(left == right)
            return lists[left];
        int mid = left + (right-left)/2;
        return merge(recurMerge(lists,left,mid), recurMerge(lists,mid+1,right));
    }
    
    public ListNode merge(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode node = head;
        while(l1 != null && l2 != null) {
            if(l1.val<=l2.val){
                node.next = l1;
                l1=l1.next;
            }else{
                node.next=l2;
                l2=l2.next;
            }
                node=node.next;
                node.next=null;
        }
        if(l1 != null)
            node.next=l1;
        if(l2 != null)
            node.next=l2;
        return head.next;
    }
}

这俩题挺好的，既考察了合并，又考察了递归与分治。

删除倒数第k个节点

思路到没啥难的，主要是一次写对不容易，区分是不是头太麻烦，自己造一个dummy！

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head==null || n<1) return null;
        ListNode dummy = new ListNode(0);
        dummy.next=head;
        ListNode fast=dummy,slow=dummy;
        slow.next=head;
        while(fast!=null && n-->=0) fast=fast.next;
        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }
        slow.next=slow.next.next;
        return dummy.next;
    }
}

循环右移

先拼成环，然后就是找倒数第k+1个，把next置null，倒数第k个是新head。感觉没优化到极致，不过思路比较清晰。

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
         if (head == null)
             return null;
        int len = 1;
        ListNode node=head;
        while(node.next!=null){
            ++len;
            node=node.next;
        }
        k %= len;
        if (k==0) return head;
        node.next=head;
        int step=len-k-1;
        node = head;
        while(--step>=0) node=node.next;
        ListNode newHead = node.next;
        node.next=null;
        return newHead;
    }
}

反转链表

应该没人还问这个了吧。。。

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null || head.next==null)
            return head;
        ListNode prev=null,node=head,next=head.next;
        while(next != null){
            node.next=prev;
            prev=node;
            node=next;
            next=next.next;
        }
        node.next=prev;
        return node;
    }
}

Remove Duplicates from Sorted List

Input: 1->1->2
Output: 1->2

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode node=head;
        while(node != null) {
            ListNode next = node.next;
            while(next != null && next.val==node.val){
                next=next.next;
            }
            node.next=next;
            node=next;
        }
        return head;
    }
}

Remove Duplicates from Sorted List II

Input: 1->2->3->3->4->4->5
Output: 1->2->5

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null)
            return null;
        ListNode dummy = new ListNode(0);
        dummy.next=head;
        ListNode node=head,prev=dummy,next=node.next;
        while(next != null){
            int step=1;
            while(next != null && next.val==node.val){
                step++;
                next=next.next;
            }  
            if(step>1){
                prev.next=next;
                node=next;

            } else {
                prev=node;
                node=next;
            }
            if(next != null)
                next=next.next;   
        }
        return dummy.next;
    }
}

Reorder List

Given 1->2->3->4, reorder it to 1->4->2->3.
思路就是先构建一个反转的链表，然后上一个下一个的拼起来，注意最后要设置next=null

class Solution {
    public void reorderList(ListNode head) {
        if(head==null)
            return ;
        ListNode node=head;
        List<Integer> arr = new ArrayList<>();
        while(node != null){
            arr.add(node.val);
            node = node.next;
        }
        int len = arr.size();
        node = head;
        ListNode next=null;
        for(int i=2; i<=len; i++){
            if(i%2==0){
                next=node.next;
                ListNode cur = new ListNode(arr.get(len-i/2));
                node.next=cur;
            } else {
                node.next=next;
            }
            node = node.next;
        }
        node.next=null;
    }
}