6/9, LinkedList，链表基础，反转与删除

写了这么久奇形怪状的数据结构，终于开始灌水了。。哈哈哈哈

LinkedList 常用操作：

• 翻转
• 找 kth element
• partition
• 排序
• 合并

常用技巧：

• dummy node
• 快慢指针
• 多个 ptr

Reverse Linked List

这种 swap 中有个很有意思的性质，如果下一行的等号左面等于上一行的等号右边，并且以第一行的等号左边结尾，那最后实际做的事情是 swap 了第一行等号右，和最后一行等号左。

public class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        while(head != null){
            ListNode temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
}

Reverse Linked List II

这题还挺 tricky 的，写了好几次。

public class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(m == n) return head;

        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode prev = dummy;
        ListNode cur = head;

        for(int i = 0; i < m - 1; i++){
            prev = prev.next;
            cur = cur.next;
        }

        for(int i = 0; i < n - m; i++){
            ListNode next = cur.next;
            cur.next = next.next;
            next.next = prev.next;
            prev.next = next;
        }


        return dummy.next;
    }
}

Remove Nth Node From End of List

涉及链表删除操作的时候，稳妥起见都用 dummy node，省去很多麻烦。因为不一定什么时候 head 就被删了。

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode slow = dummy;
        ListNode fast = dummy;
        for(int i = 0; i < n; i++){
            fast = fast.next;
        }

        while(fast.next != null){
            slow = slow.next;
            fast = fast.next;
        }

        slow.next = slow.next.next;
        return dummy.next;
    }
}

Remove Linked List Elements

这题完全是一个道理，只不过注意下没准要删除的元素是连续的，那种情况下不要动 head.

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        while(head.next != null){
            if(head.next.val == val){
                head.next = head.next.next;
            } else {
                head = head.next;
            }
        }

        return dummy.next;
    }
}

Delete Node in a Linked List

这题稍微有点怪，因为没有 prev 指针，其实只能把后边的值都给 shift 过来。。。+

既然是删除，还是用 dummy node.(不然会有 bug，[0]-->[1] 删 [0] 会返回 [1]-->[1] 而不是 [1])

public class Solution {
    public void deleteNode(ListNode node) {
        ListNode dummy = new ListNode(0);
        dummy.next = node;
        while(node.next != null){
            dummy.next.val = node.next.val;
            dummy = dummy.next;
            node = node.next;
        }
        dummy.next = null;
    }
}