合并有序链表
LeetCode 21. 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
使用类似于归并排序的思路即可，两个指针分别遍历两个链表，根据结点元素大小归并，直到某个链表遍历结束，未遍历完成的链表中的元素置于最后即可。
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode head = new ListNode();
ListNode cur = head;
ListNode cur1 = list1, cur2 = list2;
while(cur1 != null && cur2 != null) {
if(cur1.val < cur2.val) {
cur.next = cur1;
cur1 = cur1.next;
cur = cur.next;
} else {
cur.next = cur2;
cur2 = cur2.next;
cur = cur.next;
}
}
if(cur1 != null) cur.next = cur1;
if(cur2 != null) cur.next = cur2;
return head.next;
}
}
LeetCode 23. 与上题相同，但输入K个升序链表。
对于K个升序链表，使用K-1次两个链表的归并即可，这样时间复杂度为\(O(k^2n)\)。为此可以进行优化，使用分治法合并，对K个链表每次分为两部分分别合并，以此类推，时间复杂度为\(O(knlogk)\)。
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode head = new ListNode();
ListNode cur = head;
ListNode cur1 = list1, cur2 = list2;
while(cur1 != null && cur2 != null) {
if(cur1.val < cur2.val) {
cur.next = cur1;
cur1 = cur1.next;
cur = cur.next;
} else {
cur.next = cur2;
cur2 = cur2.next;
cur = cur.next;
}
}
if(cur1 != null) cur.next = cur1;
if(cur2 != null) cur.next = cur2;
return head.next;
}
public ListNode merge(ListNode[] lists, int left, int right) {
if(left == right) return lists[left];
if(left > right) return null;
int mid = left + (right - left) / 2;
return mergeTwoLists(merge(lists, left, mid), merge(lists, mid + 1, right));
}
public ListNode mergeKLists(ListNode[] lists) {
return merge(lists, 0, lists.length - 1);
}
}
反转链表
LeetCode 206. 反转链表 ：给你单链表的头节点head，请你反转链表，并返回反转后的链表。
要想原地反转链表，必须维护两个指针，一前一后指向两个结点，假设这两个指针分别为prev和cur，且满足prev.next == cur，则反转结点的步骤为：
tmp = cur;
cur = cur.next;
tmp.next = prev;
prev = tmp;
每次执行上述步骤将反转cur所指向的结点（改变其next），直到cur == null时整个链表除了最后一个结点外的结点都已反转完成，此时prev恰好指向最后一个结点，为此设prev.next = null完成最后的工作。
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null) return null;
if(head.next == null) return head;
ListNode prev = head, cur = head.next;
while(cur != null) {
ListNode tmp = cur;
cur = cur.next;
tmp.next = prev;
prev = tmp;
}
head.next = null;
return prev;
}
}
考虑链表只有一个结点，初始时prev = head而cur = null，上述代码仍能正常工作。
LeetCode 92. 反转链表 Ⅱ ：与上题相同，但只反转[left, right]范围内的结点，其中left和right为给定的结点序号（从1开始）。
本题和上题相比看似没有变化，但注意特殊情况的处理。首先根据left移动指针prev和cur，直到prev指针指向结点left，而cur指向结点left的下一个结点，因为结点left可能不是头结点，因此反转[left, right]中的结点后，我们仍需修改结点left的上一个结点，使其next指向结点right，为此我们还需记录结点left的上一个节点（如果存在）。同理，还需记录结点right的下一个结点（如果存在），并在反转后使结点left的next指向该节点，不过并不需要提前遍历来搜索该结点，因为反转完成后cur恰好指向该节点。
反转完成后链表的头结点如何确定？注意如果left == 1那么反转前后头节点会发生改变，新的头节点为节点right，如果 left > 1那么反转后头节点不变。
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
if(head == null) return null;
if(head.next == null) return head;
ListNode prev = head, cur = null;
ListNode prevLeftNode = null, leftNode = null;
if(left == 1) { //结点left为头结点
prevLeftNode = null;
leftNode = prev;
} else { //结点left不是头结点，先搜索结点left的上一个结点
for(int i = 0; i < left - 2; i++) {
prev = prev.next;
}
prevLeftNode = prev;
leftNode = prev.next;
prev = prev.next;
}
cur = prev.next;
int k = 0;
while(k < right - left) {
ListNode tmp = cur;
cur = cur.next;
tmp.next = prev;
prev = tmp;
k++;
}
leftNode.next = cur; //反转后的末端连接
if(prevLeftNode != null) prevLeftNode.next = prev; //反转后的始端连接
return left == 1 ? prev : head; //返回头结点
}
}
LeetCode 25. K个一组翻转链表 ：
给你链表的头节点head，每k个节点一组进行翻转，请你返回修改后的链表。k是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
本题要处理几件事：（1）对每一组k个节点进行反转。（2）反转一组k个节点后需将其与上一组的最后一个结点相连接。（3）对于不足k个结点的一组不予反转。
为了反转每一组k个节点，可以实现如下函数反转链表的某个特定部分，该函数接收反转部分的第一个结点和最后一个结点，并返回反转后的第一个结点和最后一个结点：
public ListNode[] reverse(ListNode head, ListNode tail) {
if(head == null) return new ListNode[] {null, null};
if(head == tail) return new ListNode[] {head, head};
ListNode prev = head, cur = head.next;
while(prev != tail) {
ListNode tmp = cur;
cur = cur.next;
tmp.next = prev;
prev = tmp;
}
head.next = null;
return new ListNode[] {tail, head};
}
为此我们需要搜索每一组的第一个结点和最后一个结点，这也可以帮助我们判断这一组是否不足k个结点，因为反转后各个结点的next均已改变，因此最好提前确定好下一组的第一个结点。由于反转后需要连接上一组（如果存在）的最后一个结点，因此还需记录上一组的最后一个结点。
考虑整个链表的第一个结点可能被反转也可能没有被反转，返回的头结点有所不同。
/**
* 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; }
* }
*/
class Solution {
public ListNode[] reverse(ListNode head, ListNode tail) {
if(head == null) return new ListNode[] {null, null};
if(head == tail) return new ListNode[] {head, head};
ListNode prev = head, cur = head.next;
while(prev != tail) {
ListNode tmp = cur;
cur = cur.next;
tmp.next = prev;
prev = tmp;
}
head.next = null;
return new ListNode[] {tail, head};
}
public ListNode reverseKGroup(ListNode head, int k) {
//当前组反转前的第一个结点
ListNode groupFirst = head;
//当前组反转前的最后一个结点
ListNode groupLast = null;
//上一组反转后的最后一个结点
ListNode lastGroupLast = null;
//下一组反转前的第一个结点
ListNode nextGroupFirst = null;
//第一组反转后的第一个结点
//如果第一组未反转该值保持NULL
ListNode firstGroupFirst = null;
while(groupFirst != null) {
//搜索当前组的最后一个结点和下一组的第一个结点
nextGroupFirst = groupFirst;
//该行代码不能省略，这是为了保证k==1时groupLast的取值正确
groupLast = groupFirst;
for(int i = 0; i < k; i++) {
nextGroupFirst = nextGroupFirst.next;
//搜索即将结束但不足k个结点说明反转完成，注意如果即将结束时i=-k-1说明最后一组恰好为k个结点
if(nextGroupFirst == null && i < k - 1) {
//如果第一组未反转返回head
//如果第一组已反转返回新的头节点
return firstGroupFirst == null ? head : firstGroupFirst;
}
//i==k-1时为下一组反转前的第一个结点
//i==k-2时为当前组反转前的最后一个结点
//该行代码只有k>=2时才会执行
if(i == k - 2) groupLast = nextGroupFirst;
}
//反转当前组
ListNode[] reverse = reverse(groupFirst, groupLast);
//记录第一组反转后的第一个结点
if(firstGroupFirst == null) firstGroupFirst = reverse[0];
//连接上一组反转后的最后一个结点
if(lastGroupLast != null) lastGroupLast.next = reverse[0];
//连接下一组反转前的第一个结点
//虽然每次反转后都会连接上一组反转后的最后一个结点
//但这句代码不能省略：
//（1）如果最后不足k个结点那么不会反转，该行代码保证它们是连接的。
//（2）如果最后一组恰好一共k个节点，该行代码保证最后一个节点的next指向NULL。
reverse[1].next = nextGroupFirst;
//即将反转下一组
groupFirst = nextGroupFirst;
//更新上一组反转后的最后一个结点
lastGroupLast = reverse[1];
}
//返回头结点
return firstGroupFirst == null ? head : firstGroupFirst;
}
}
重排链表
LeetCode 148. 排序链表 ：给你链表的头结点head，请将其按升序排列并返回排序后的链表。
由于链表不支持随机访问，因此相比于排序数组具有较强的局限性，对于链表来说最合适的排序算法只要有三种：归并排序、插入排序和快速排序。
若使用归并排序，核心原理是对两个有序链表进行归并，利用递归可以实现置顶向下不停地将链表分为两部分，对两部分分别排序（这里进行了递归），然后归并这两部分，为了将链表分为两部分，需要使用快慢指针找到链表的中点。
对两个有序链表进行归并的方法如下：
private ListNode MergeList(ListNode head1, ListNode head2) {
ListNode head = new ListNode();
ListNode cur = head;
ListNode cur1 = head1, cur2 = head2;
while(cur1 != null && cur2 != null) {
if(cur1.val < cur2.val) {
cur.next = cur1;
cur = cur.next;
cur1 = cur1.next;
} else {
cur.next = cur2;
cur = cur.next;
cur2 = cur2.next;
}
}
if(cur1 != null) cur.next = cur1;
else if(cur2 != null) cur.next = cur2;
return head.next;
}
利用快慢指针将链表分为两部分的方法如下，循环结束后slow指针将指向链表的中点，如果链表有奇数个结点那么slow将指向中间的结点，如果链表有偶数个结点那么slow将指向中间偏左的结点。这里切断链表的方式是直接执行slow.next = null。
ListNode fast = head.next, slow = head; //注意fast先走一步，这是为了适应链表只有两个结点的情况
while(fast != null && fast.next != null) { //fast先行，所以循环条件以fast为准
slow = slow.next; //slow一次走一步
fast = fast.next.next; //fast一次走两步
}
ListNode rhead = slow.next; //第二部分链表的第一个结点
slow.next = null;
置顶向下排序链表的完整方法如下，该方法的时间复杂度是O(nlogn)。
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int val=0, ListNode next=null) {
* this.val = val;
* this.next = next;
* }
* }
*/
public class Solution {
private ListNode MergeList(ListNode head1, ListNode head2) {
ListNode head = new ListNode();
ListNode cur = head;
ListNode cur1 = head1, cur2 = head2;
while(cur1 != null && cur2 != null) {
if(cur1.val < cur2.val) {
cur.next = cur1;
cur = cur.next;
cur1 = cur1.next;
} else {
cur.next = cur2;
cur = cur.next;
cur2 = cur2.next;
}
}
if(cur1 != null) cur.next = cur1;
else if(cur2 != null) cur.next = cur2;
return head.next;
}
public ListNode SortList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode fast = head.next, slow = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode rhead = slow.next;
slow.next = null;
ListNode left = SortList(head);
ListNode right = SortList(rhead);
return MergeList(left, right);
}
}
若使用快速排序，核心在于确定一个枢纽，简单起见可以直接以链表的第一个结点为枢纽，然后遍历其它结点：将结点值比枢纽小的结点插入到枢纽之前，将结点值比枢纽大的结点插入到枢纽之后，但链表和数组有所不同，为了便于插入，我们将记录已处理的结点串（即枢纽结点和已经和枢纽比较过的结点组成的链表）的首尾结点（通过两个指针记录，分别为lcur和rcur），这样就可以使用头插法和尾插法快速插入结点。
当一轮遍历结束后，以枢纽为界，左边的所有结点其值均小于枢纽值，而右边所有结点其值均大于枢纽值，并且lcur将指向左边的第一个结点，而rcur将指向右边的最后一个结点。随后对左右两部分（除枢纽外）进行递归即可。
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int val=0, ListNode next=null) {
* this.val = val;
* this.next = next;
* }
* }
*/
public class Solution {
//对链表区间[start, end)进行Partition，注意这将不会考虑end结点
//返回值表示Partition结束后该区间的第一个结点
private ListNode QuickSort(ListNode start, ListNode end) {
//由于不考虑end结点，因此当start.next==end时可直接返回
if(start == end || start.next == end) return start;
//取第一个结点为枢纽
int pivot = start.val;
//lcur和rcur记录已比较过的结点串的首尾结点，而cur遍历未比较过的结点
//注意cur=start.next，即初始时从枢纽的下个结点开始比较
ListNode lcur = start, rcur = start, cur = start.next;
//当cur==end时表示区间[start, end)内的所有结点均已比较
while(cur != end) {
//记录cur的下一个结点，以便下一轮循环
ListNode next = cur.next;
if(cur.val < pivot) {
//头插法插入小于枢纽值的结点
cur.next = lcur;
lcur = cur;
} else {
//尾插法插入大于等于枢纽值的结点
rcur.next = cur;
rcur = cur;
}
//更新cur
cur = next;
}
//由于是对区间[start, end)进行Partition，所以需要保证最后一个结点和end结点是连接的，这也是不考虑end的原因
rcur.next = end;
//对左边部分进行递归，不考虑枢纽start，区间为[lcur, start)
ListNode head = QuickSort(lcur, start);
//对右边部分进行递归，不考虑枢纽start，且需要考虑rcur，区间为[start.next, rcur.next)
//此处需要将返回值赋给start.next，这是因为Partition后右边部分的第一个结点已经发生变化
start.next = QuickSort(start.next, rcur.next);
return head;
}
public ListNode SortList(ListNode head) {
return QuickSort(head, null);
}
}