1. 去重单链表中出现两次及以上的所有节点

https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

// AC: Runtime: 1 ms, faster than 27.17% of Java online submissions for Remove Duplicates from Sorted List II.
// Memory Usage: 38.6 MB, less than 34.10% of Java online submissions for Remove Duplicates from Sorted List II.
// .
// T:O(n), S:O(n)
// 
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        HashSet<Integer> dup = new HashSet<>();
        ListNode headCopy = head;
        int prev = Integer.MIN_VALUE;
        while (headCopy != null) {
            if (headCopy.val == prev) {
                dup.add(headCopy.val);
            }
            prev = headCopy.val;
            headCopy = headCopy.next;
        }

        ListNode headCopy2 = head, prevNode = head;
        while (headCopy2 != null && headCopy2.next != null) {
            if (dup.contains(headCopy2.val)) {
                headCopy2.val = headCopy2.next.val;
                headCopy2.next = headCopy2.next.next;
            } else {
                prevNode = headCopy2;
                headCopy2 = headCopy2.next;
            }
        }
        // handle the head pointer itself
        if (headCopy2 != null && dup.contains(headCopy2.val)) {
            if (headCopy2 == head) {
                return null;
            }
            prevNode.next = null;
        }

        return head;
    }
}
2.链表拼接:

https://leetcode.com/problems/merge-in-between-linked-lists/

// AC: Runtime: 1 ms, faster than 100.00% of Java online submissions for Merge In Between Linked Lists.
// Memory Usage: 42.8 MB, less than 72.32% of Java online submissions for Merge In Between Linked Lists.
// record the cut start nodes and end nodes, and concatenate them to the list2
// T:O(m + n), S:O(1)
// 
class Solution {
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode head = list1, list1Start, list1End;
        int aCopy = a;
        // move to the prev node by the nodes cut first.
        while (aCopy-- > 1) {
            list1 = list1.next;
        }
        list1Start = list1;
        // move the the end nodes after cut [a,b]
        int length = b - a + 2;
        while (length-- > 0) {
            list1Start = list1Start.next;
        }
        list1End = list1Start;

        list1.next = list2;
        // move list2 to its end, the point to list1's cut end node.
        while (list2.next != null) {
            list2 = list2.next;
        }
        list2.next = list1End;

        return head;
    }
}
3.链表累加和

https://leetcode.com/problems/add-two-numbers-ii/

思路:先反转链表,拿到两个数字链表的尾节点,再从个位数开始累加,依次进位输出。 注意返回结果是高位在前!

// AC: Runtime: 2 ms, faster than 98.16% of Java online submissions for Add Two Numbers II.
// Memory Usage: 39.3 MB, less than 68.00% of Java online submissions for Add Two Numbers II.
// first reverse, then accumulate the two numbers. Notice that the answer is reversed output, that is high bit is in the front.
// T:O(n), S:O(n)
// 
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode start1 = reverseList(l1), start2 = reverseList(l2), retHead;
        List<Integer> ret = new ArrayList<>();
        int forwarding = 0;
        while (start1 != null || start2 != null) {
            int bit1 = 0, bit2 = 0;
            if (start1 != null) {
                bit1 = start1.val;
                start1 = start1.next;
            }
            if (start2 != null) {
                bit2 = start2.val;
                start2 = start2.next;
            }
            if (bit1 + bit2 + forwarding >= 10) {
                ret.add((bit1 + bit2 + forwarding) % 10);
                forwarding = 1;
            } else {
                ret.add(bit1 + bit2 + forwarding);
                forwarding = 0;
            }
        }
        if (forwarding > 0) {
            ret.add(forwarding);
        }
        retHead = new ListNode(ret.get(ret.size() - 1));
        ListNode copy = retHead;
        for (int i = ret.size() - 2; i >= 0; i--) {
            ListNode next = new ListNode(ret.get(i));
            copy.next = next;
            copy = next;
        }

        return retHead;
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null, temp = head;
        while (head != null) {
            temp = head.next;
            head.next = prev;
            prev = head;
            head = temp;
        }

        return prev;
    }
}
4.leetcode328-将链表奇数位和偶数位分开排列再相连

https://leetcode.com/problems/odd-even-linked-list/

思路:创建两个链表头, oddHead, evenHead,按链表递进次序分开拼接两个链表。注意只是改变原 ListNode 的指向,因此并不占用额外空间。最后将最后一个 odd 节点赋值 odd.next = evenHead,此时的 oddHead 即为结果。

// AC: Runtime: 0 ms, faster than 100.00% of Java online submissions for Odd Even Linked List.
// Memory Usage: 38.6 MB, less than 60.27% of Java online submissions for Odd Even Linked List.
// divide the original linked-list into odd-list and even-list, and concat even-list to end of odd-list.
// T:O(n), S:O(1)
// 
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head != null) {
            ListNode odd = head, even = head.next, oddHead = odd, 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;
    }
}
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */