LinkedList基本操作

• 翻转链表
• 删除元素
• 找中点
• partition
• 排序
• 合并
• 第k个元素

常用技巧：

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

Reverse Linked List

recursive 写法

public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }

        ListNode next = head.next;
        ListNode newHead = reverseList(head.next);
        next.next = head;
        head = null;

        return newHead;
    }

Iterative 写法

这种写法一个有意思的点是： 如果下一行的等号左面等于上一行的等号右边，并且以第一行的等号左边结尾，那最后实际做的事情是 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

交换第m个到第n个

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

        ListNode pre = dummy;
        ListNode cur = head;
        // start from 1
        for(int i = 0; i < m - 1; i++) {
            pre = pre.next;
            cur = cur.next;
        }

        // 一次交换影响两个点
        // prev和cur是定住的
        // 变化的是next
        for(int i = 0; i < n - m; i++) {
            ListNode next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }

        return dummy.next;       
    }
}

83. Remove Duplicates from Sorted List

因为是删除duplicate，所以第一个node是不可能删除的，所以我们可以不需要dummy node来做这一题。

用两个指针pre和cur，分别代表最后一个不重复的node和下一个需要比较的node

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        // 最后一个不重复的node
        ListNode pre = head;
        ListNode cur = head.next;

        while(cur != null) {
            while (cur != null && pre.val == cur.val) {
                cur = cur.next;
            }
            pre.next = cur;
            pre = pre.next;
            if(cur != null) {
                cur = cur.next;
            }
        }

        return head;

    }
}

Remove Duplicates from Sorted List II

删除所有的重复的节点，只保留没有过重复数字的节点

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }

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

        ListNode pre = dummy;
        ListNode cur = dummy.next;

        while(cur != null) {
            // mark cur.next != null
            // the goal of cur is find the last dups node
            while(cur.next != null && cur.val == cur.next.val) {
                cur = cur.next;
            }
            // if no dups
            if(pre.next == cur) {
                pre = pre.next;
            } else {
                pre.next = cur.next;
            }
            cur = cur.next;
        }
        return dummy.next;
    }
}

Remove Linked List Elements

public class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head == null) {
            return null;
        }

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

        ListNode pre = dummy;
        ListNode cur = dummy.next;

        while(cur != null) {
            // find the node
            if(cur.val == val) {
                // delete node
                pre.next = cur.next;
            } else {
                // nothing happen
                pre = pre.next;
            }
            cur = cur.next;
        }

        return dummy.next;
    }
}

Reverse Nodes in k-Group

题意：以k个node为一组进行翻转

关键是要保存要翻转的group之前的节点，和之后的节点。

// 如何翻转内部的k个节点
while(cur != end) {
    ListNode post = cur.next;
    cur.next = pre.next;
    pre.next = cur; // 为了让pre指向最后一个元素
    cur = post;
}

carry

369. Plus One Linked List

while(cur != null) {
    int sum = cur.val + carry;
    cur.val = sum % 10;
    carry = sum / 10;

    // if the last number is 9 + 1, we need to add a new node at the end.
    if(cur.next == null && carry != 0) {
       cur.next = new ListNode(carry);
       break;
    }
    cur = cur.next;
}