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; }
* }
*/