单链表的归并排序和插入排序
程序员文章站
2024-03-17 23:50:28
...
由于最近在学习数据结构和算法,在牛客网 的在线编程题上遇到了对链表的相关排序操作,发现自己对链表这块还是理解不够深入,以前做过对数组进行排序,但链表的操作要比数组复杂一些,毕竟不能进行随机访问了,单链表得从头开始找。
下面是我通过在线编程(OJ)代码并附有注释。
1.单链表的归并排序
1.题目
Sort a linked list in O(n log n) time using constant space complexity.
对一个链表进行排序,要求时间复杂度为O(n log n)
2.解题思路
题目要求时间复杂度为nlog(n),所以选择了归并排序。归并排序最坏时间复杂度、平均时间复杂度、最快时间复杂度都为nlog(n)。它是一种稳定的排序算法。
链接:思路来源
来源:牛客网
2.1 拆分链表,找到中间节点
用快慢指针的方式,快指针移动两位,慢指针移动一位。
/** 查找中间结点 */
public ListNode findMidNode(ListNode head){
ListNode p= head;
ListNode q=head.next;
while (q != null && q.next != null) {
p = p.next;
q = q.next.next;
}
return p;
}
2.2分治,分别处理每个链表
ListNode midNode =findMidNode(head);
ListNode record = midNode.next;
midNode.next = null; //断开两个链表的连接
ListNode left = MySort(head, midNode);
ListNode right = MySort(record, end);
2.3合并
/** 合并左右链表 */
private ListNode merge(ListNode left, ListNode right) {
if(left==null)return right;
if(right==null)return left;
ListNode newhead = null;
newhead=new ListNode(0);
ListNode temp = newhead;
while (left != null && right != null) {
if (left.val > right.val) {
temp.next= right;
right= right.next;
} else {
temp.next= left;
left = left.next;
}
temp=temp.next;
}
temp.next=(left==null)?right:left;
return newhead.next;
}
3. 完整代码
/**
* Definition for singly-linked list.
* class ListNode {
* int val; ListNode next;
* ListNode(int x) {
* val = x; next = null;
* }
*} //排序算法选择归并排序
*/
public class Solution {
private ListNode indexNode =new ListNode(Integer.MAX_VALUE);
public ListNode sortList(ListNode head) {
if (head == null) {
return head;
}
return MySort(head, null);
}
private ListNode MySort(ListNode head, ListNode end) {
if(head==end){
return head;
}
ListNode midNode =findMidNode(head);
ListNode record = midNode.next;
midNode.next = null;
ListNode left = MySort(head, midNode);
ListNode right = MySort(record, end);
return merge(left, right);
}
/** 查找中间结点 */
public ListNode findMidNode(ListNode head){
ListNode p= head;
ListNode q=head.next;
while (q != null && q.next != null) {
p = p.next;
q = q.next.next;
}
return p;
}
/** 合并左右链表 */
private ListNode merge(ListNode left, ListNode right) {
if(left==null)return right;
if(right==null)return left;
ListNode newhead = null;
newhead=new ListNode(0);
ListNode temp = newhead;
while (left != null && right != null) {
if (left.val > right.val) {
temp.next= right;
right= right.next;
} else {
temp.next= left;
left = left.next;
}
temp=temp.next;
}
temp.next=(left==null)?right:left;
return newhead.next;
}
public static void main(String[] args) {
ListNode list = new ListNode(4);
ListNode head = list;
head.next = new ListNode(2);
head.next.next = new ListNode(1);
head.next.next.next = new ListNode(3);
Solution solution = new Solution();
ListNode result = solution.sortList(head);
while (result != null) {
System.out.print(result.val + "\t");
result = result.next;
}
}
public void display(ListNode result) {
while (result != null) {
System.out.print(result.val + "\t");
result = result.next;
}
System.out.println();
}
}
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
2.单链表的直接插入排序
1.题目
Sort a linked list using insertion sort.
2.注意事项
每次的插入操作时,需要保留下一结点。
然后用伪首结点该结点值为最小值,将他们串联起来。
完整代码
public class Solution {
public ListNode insertionSortList(ListNode head) {
if (head == null || head.next == null) // 链表为空或者仅一个结点
return head;
ListNode saveNode = new ListNode(Integer.MIN_VALUE);
// ListNode current =head;
ListNode previous = saveNode;
while (head != null) {
ListNode next = head.next;
previous = saveNode; // 每次都从新链表的头结点进行遍历
while (previous.next != null && previous.next.val < head.val) {
previous = previous.next;
}
if (previous == saveNode) { // 链表为空时
head.next = previous.next;
previous.next=head;
} else if(previous.next==null){ //尾部结点时
head.next = previous.next;
previous.next=head;
}
else { //中间插入
ListNode nextnext=previous.next;
head.next=nextnext;
previous.next=head;
}
head = next;
}
return saveNode.next;
}
public void display(ListNode node) {
while (node != null) {
System.out.print(node.val + "\t");
node = node.next;
}
}
}
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}