今日主題：鏈表。
147. 對鏈表進行插入排序
問題描述
對鏈表進行插入排序。
解題思路
- 添加虛擬頭節(jié)點，保證對鏈表節(jié)點操作的一致性
- 注意切斷頭節(jié)點與后續(xù)節(jié)點的指針，不然會形成環(huán)形鏈表
代碼實現(xià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 insertionSortList(ListNode head) {
if(head == null){
return head;
}
//添加虛擬頭節(jié)點，指向新的已排好序的鏈表
ListNode dummyHead = new ListNode(0);
//將頭節(jié)點的值加入已排好序的鏈表;避免形成環(huán)形鏈表
dummyHead.next = new ListNode(head.val);
ListNode cur = head.next;
while(cur != null){
//temp保存當前節(jié)點的下一個節(jié)點
ListNode temp = cur.next;
//從頭開始遍歷已經(jīng)排好序的鏈表，找到插入位置
ListNode pre = dummyHead, index = dummyHead.next;;
while(index != null && index != cur){
if(cur.val < index.val){
break;
}
pre = pre.next;
index = index.next;
}
//如果退出循環(huán)時，index==null，表示當前值比之前所有的值都大，不需要進行插入
//index != null, 需要進行節(jié)點插入
if(index != cur){
pre.next = cur;
cur.next = index;
}
cur = temp;
}
return dummyHead.next;
}
}
21. 合并兩個有序鏈表
問題描述
將兩個升序鏈表合并為一個新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的。
解題思路
應用歸并排序合并數(shù)組的思想。
代碼實現(xià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 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) 時間復雜度和常數(shù)級空間復雜度下，對鏈表進行排序嗎？
解題思路
時間復雜度為O(n log n)的常見排序算法有：快排、堆排、歸并。
其中快排和堆排設計到的元素交換操作較多，而對單鏈表中的兩個任意節(jié)點進行交換，操作比較復雜。正好，歸并排序算法中合并左右有序數(shù)組的操作有用到雙指針。因此，采用歸并排序實現(xiàn)。
代碼實現(xià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);
}
//采用快慢指針找到鏈表的中點(偶數(shù)節(jié)點返回偏左節(jié)點)
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;
}
}
