Swap Nodes in Pairs
思路：需要构造一个头指针，指向链表。一次比较两个指针，将其翻转，临界条件是pre != null(链表长度为偶数) && pre.next != null(链表长度为奇数)，然后更新头指针和pre
public ListNode swapPairs(ListNode head) {
if(head == null) return null;
ListNode newNode = new ListNode(0);
ListNode node = newNode;
node.next = head;
ListNode ptr = head;
while(ptr != null && ptr.next != null){
node.next = ptr.next;
ptr.next = ptr.next.next;
node.next.next = ptr;
node = node.next.next;
ptr = ptr.next;
}
return newNode.next;
}
Insertion Sort List
思路：构造一个头指针node，指向结果链表。每次取出head和结果链表中的节点val进行比较，知道找到应该插入的位置，插入，然后重置node和head
public ListNode insertionSortList(ListNode head) {
if(head == null) return null;
ListNode node = new ListNode(0);
while(head != null){
ListNode pre = node;
while(pre.next != null && pre.next.val <= head.val){
pre = pre.next;
}
ListNode temp = head.next;
head.next = pre.next;
pre.next = head;
head = temp;
}
return node.next;
}
Odd Even Linked List
思路：依次取出奇数位节点和偶数位节点，然后将奇数尾和偶数头连接起来
public ListNode oddEvenList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode odd = head;
ListNode even = head.next;
ListNode temp = even;
while(even != null && even.next != null){
odd.next = even.next;
odd = odd.next;
even.next = odd.next;
even = even.next;
}
odd.next = temp;
return head;
}
Remove Duplicates from Sorted List II
思路：构造一个头结点指向链表，后面利用双指针判断val是否一致，若不一致则三个指针同时后移，若一直则尾指针后移直到不一致，利用头指针跳过所有重复的节点。
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null) return head;
ListNode ptr = new ListNode(0);
ptr.next = head;
ListNode copy = ptr;
ListNode pre = head;
ListNode pos = head.next;
while(pos != null){
if(pos.val != pre.val){
ptr = ptr.next;
pre = pre.next;
pos = pos.next;
}
else{
while(pos != null && pos.val == pre.val){
pos = pos.next;
}
ptr.next = pos;
if(pos != null){
pre = pos;
pos = pos.next;
}
}
}
//ptr.next = null;
return copy.next;
}
Merge k Sorted Lists
思路：利用归并的思想，依次将链表的列表从中间分开，然后依次合并两个已排好序的链表
public ListNode mergeKLists(ListNode[] lists) {
int len = lists.length;
if(len == 0) return null;
return helper(lists,0,len - 1);
}
public ListNode helper(ListNode[] lists,int l,int r){
if(l < r){
int m = l + (r - l) / 2;
return merge(helper(lists,l,m),helper(lists,m + 1,r));
}
return lists[l];
}
public ListNode merge(ListNode l1,ListNode l2){
if(l1 == null) return l2;
if(l2 == null) return l1;
if(l1.val < l2.val){
l1.next = merge(l1.next,l2);
return l1;
}
else{
l2.next = merge(l1,l2.next);
return l2;
}
}
类似的：Sort List，也是归并的思想
Reverse Nodes in k-Group
思路：构造一个头指针指向链表，依次往后当长度等于k时，则翻转链表，这个过程注意需要保存要翻转链表的头结点
public ListNode reverseKGroup(ListNode head, int k) {
ListNode ptr = new ListNode(0);
ptr.next = head;
ListNode ptr1 = ptr;
ListNode curNode = head;
int cnt = 0;
while(curNode != null){
ListNode left = head;
cnt++;
if(cnt == k){
ListNode tail = curNode.next;
curNode.next = null;
ListNode leftCopy = left;
reverse(ptr1,left,curNode);
leftCopy.next = tail;
curNode = tail;
head = curNode;
ptr1 = leftCopy;
cnt = 0;
continue;
}
curNode = curNode.next;
}
return ptr.next;
}
public void reverse(ListNode ptr1,ListNode left,ListNode right){
ListNode p = null;
ListNode q = left;
while(left != right){
left = left.next;
q.next = p;
p = q;
q = left;
}
left.next = p;
ptr1.next = left;
}
141 双指针，一个快，一个慢，若过程中两指针相同则有环
19/61 双指针，相隔n
21 递归
160 得到两个链表的长度，重置长链表起点使之和短链表一致直到同时达到连接点
83/203 双指针
206 翻转指针
92 找到要翻转指针的范围，翻转
2/445 首先判断两链表长度，将长的那个作为被加数，即最终一定是加数先置为null，然后一位位相加，注意进位，然后判断是否多余的位上val都是9的情况，最后判断是否需要增加尾指针的情况；445比2多了一个翻转操作
86 构造两个头结点，分别表示不小于x的链表和小于x的链表，依次构造完以后拼接起来
常用的小模块和方法：
- 翻转链表
- 快慢指针得到链表中点
- 构造一个节点指向头结点
练习：
Palindrome Linked List：找到中点、翻转指针、依次比较
Delete Node in a Linked List：只能从要删除节点入手，则依次用后节点的val覆盖前节点的val
Reorder List：找到中点、翻转指针、依次连接
Linked List Cycle II：快慢指针找到相遇的位置，然后一个从head位置走，一个从相遇位置走，在环节点处相遇（注意没环的情况）
Convert Sorted List to Binary Search Tree：快慢指针找中点即头结点，递归建树
链表需注意：判头判尾是否为空、写到.next .val判断当前指针是否为空