今日主题：链表。
147. 对链表进行插入排序
问题描述
对链表进行插入排序。
解题思路
- 添加虚拟头节点，保证对链表节点操作的一致性
- 注意切断头节点与后续节点的指针，不然会形成环形链表
代码实现
/**
* 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 insertionSortList(ListNode head) {
if(head == null){
return head;
}
//添加虚拟头节点，指向新的已排好序的链表
ListNode dummyHead = new ListNode(0);
//将头节点的值加入已排好序的链表;避免形成环形链表
dummyHead.next = new ListNode(head.val);
ListNode cur = head.next;
while(cur != null){
//temp保存当前节点的下一个节点
ListNode temp = cur.next;
//从头开始遍历已经排好序的链表，找到插入位置
ListNode pre = dummyHead, index = dummyHead.next;;
while(index != null && index != cur){
if(cur.val < index.val){
break;
}
pre = pre.next;
index = index.next;
}
//如果退出循环时，index==null，表示当前值比之前所有的值都大，不需要进行插入
//index != null, 需要进行节点插入
if(index != cur){
pre.next = cur;
cur.next = index;
}
cur = temp;
}
return dummyHead.next;
}
}
21. 合并两个有序链表
问题描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
解题思路
应用归并排序合并数组的思想。
代码实现
/**
* 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 mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0);
ListNode tail = head;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
tail.next = new ListNode(l1.val);
l1 = l1.next;
}else {
tail.next = new ListNode(l2.val);
l2 = l2.next;
}
tail = tail.next;
}
// 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
tail.next = l1 == null ? l2 : l1;
return head.next;
}
}
148. 排序链表
问题描述
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
解题思路
时间复杂度为O(n log n)的常见排序算法有：快排、堆排、归并。
其中快排和堆排设计到的元素交换操作较多，而对单链表中的两个任意节点进行交换，操作比较复杂。正好，归并排序算法中合并左右有序数组的操作有用到双指针。因此，采用归并排序实现。
代码实现
/**
* 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 sortList(ListNode head) {
if(head == null || head.next == null){
return head;
}
//将链表拆分为左右两段
ListNode mid = getMid(head);
ListNode rightHead = mid .next;
mid.next = null;
//得到有序左、右子链表
ListNode sortedLeft = sortList(head);
ListNode sortRight = sortList(rightHead);
//合并左右子链表
return mergeTwoLists(sortedLeft,sortRight);
}
//采用快慢指针找到链表的中点(偶数节点返回偏左节点)
public ListNode getMid(ListNode head){
ListNode dummyHead = new ListNode(0,head);
ListNode slow = dummyHead, fast = dummyHead;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
//合并两个有序链表
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0);
ListNode tail = head;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
tail.next = new ListNode(l1.val);
l1 = l1.next;
}else {
tail.next = new ListNode(l2.val);
l2 = l2.next;
}
tail = tail.next;
}
// 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
tail.next = l1 == null ? l2 : l1;
return head.next;
}
}
