题目LeetCode148给你链表的头结点head请将其按升序排列并返回排序后的链表。示例输入head [4,2,1,3]输出[1,2,3,4]此题如果用正常头插尾插法会超时此题不做说明Python解法1.利用sort方法此方法比较偷懒可以看看可以通过# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def sortList(self, head: Optional[ListNode]) - Optional[ListNode]: arr [] p head while p: arr.append(p.val) p p.next arr.sort() p head idx 0 while p: p.val arr[idx] idx 1 p p.next return head2.归并递归# 链表节点定义 class ListNode: def __init__(self, val0, nextNone): self.val val self.next next class Solution: def sortList(self, head: ListNode) - ListNode: # 递归终止空链表 / 单节点链表天然有序 if not head or not head.next: return head # 获取中点拆分左右链表 mid self.findMiddle(head) right_head mid.next mid.next None # 断开中点分割左右 # 递归分治排序左右子链表 left_sorted self.sortList(head) right_sorted self.sortList(right_head) # 合并两个有序链表并返回 return self.mergeTwoLists(left_sorted, right_sorted) # 快慢指针找左中点 def findMiddle(self, head: ListNode) - ListNode: slow head fast head.next # fast起步在后保证slow停在左中点 while fast and fast.next: slow slow.next fast fast.next.next return slow # 合并两条有序单向链表 def mergeTwoLists(self, l1: ListNode, l2: ListNode) - ListNode: dummy ListNode(-1) cur dummy while l1 and l2: if l1.val l2.val: cur.next l1 l1 l1.next else: cur.next l2 l2 l2.next cur cur.next # 拼接剩余部分 cur.next l1 if l1 else l2 return dummy.next过程演示Java解法仅说明归并代码示例public ListNode sortList(ListNode head) { // 递归终止条件链表为空或只有一个节点 if (head null || head.next null) { return head; } // 找到链表的中点 ListNode mid findMiddle(head); ListNode rightHead mid.next; // 右半部分的头节点 mid.next null; // 断开链表 // 递归排序左半部分和右半部分 ListNode left sortList(head); ListNode right sortList(rightHead); // 合并两个有序链表 return mergeTwoLists(left, right); } // 找到链表的中点快慢指针法 private ListNode findMiddle(ListNode head) { ListNode slow head; ListNode fast head.next; // fast 从 head.next 开始确保 slow 指向中点或左中点 while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } return slow; } // 合并两个有序链表 private ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy new ListNode(-1); // 虚拟头节点 ListNode curr dummy; while (l1 ! null l2 ! null) { if (l1.val l2.val) { curr.next l1; l1 l1.next; } else { curr.next l2; l2 l2.next; } curr curr.next; } // 将剩余的链表接上 if (l1 ! null) { curr.next l1; } if (l2 ! null) { curr.next l2; } return dummy.next; }改为PythonC解法同Java代码示例struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; class Solution { public: ListNode* sortList(ListNode* head) { // 递归终止条件 if (head nullptr || head-next nullptr) { return head; } // 找中点 ListNode* mid findMiddle(head); ListNode* rightHead mid-next; mid-next nullptr; // 递归排序左右两部分 ListNode* left sortList(head); ListNode* right sortList(rightHead); // 合并有序链表 return mergeTwoLists(left, right); } private: // 快慢指针找左中点 ListNode* findMiddle(ListNode* head) { ListNode* slow head; ListNode* fast head-next; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; } return slow; } // 合并两个有序链表使用三目运算符简化收尾 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(-1); ListNode* curr dummy; while (l1 ! nullptr l2 ! nullptr) { if (l1-val l2-val) { curr-next l1; l1 l1-next; } else { curr-next l2; l2 l2-next; } curr curr-next; } // C 同样支持三目运算符 curr-next l1 ? l1 : l2; return dummy.next; } };注意Java的三目运算不能省略nullJava 中对象引用不能直接当成布尔条件
LeetCode148：链表排序终极解法
题目LeetCode148给你链表的头结点head请将其按升序排列并返回排序后的链表。示例输入head [4,2,1,3]输出[1,2,3,4]此题如果用正常头插尾插法会超时此题不做说明Python解法1.利用sort方法此方法比较偷懒可以看看可以通过# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def sortList(self, head: Optional[ListNode]) - Optional[ListNode]: arr [] p head while p: arr.append(p.val) p p.next arr.sort() p head idx 0 while p: p.val arr[idx] idx 1 p p.next return head2.归并递归# 链表节点定义 class ListNode: def __init__(self, val0, nextNone): self.val val self.next next class Solution: def sortList(self, head: ListNode) - ListNode: # 递归终止空链表 / 单节点链表天然有序 if not head or not head.next: return head # 获取中点拆分左右链表 mid self.findMiddle(head) right_head mid.next mid.next None # 断开中点分割左右 # 递归分治排序左右子链表 left_sorted self.sortList(head) right_sorted self.sortList(right_head) # 合并两个有序链表并返回 return self.mergeTwoLists(left_sorted, right_sorted) # 快慢指针找左中点 def findMiddle(self, head: ListNode) - ListNode: slow head fast head.next # fast起步在后保证slow停在左中点 while fast and fast.next: slow slow.next fast fast.next.next return slow # 合并两条有序单向链表 def mergeTwoLists(self, l1: ListNode, l2: ListNode) - ListNode: dummy ListNode(-1) cur dummy while l1 and l2: if l1.val l2.val: cur.next l1 l1 l1.next else: cur.next l2 l2 l2.next cur cur.next # 拼接剩余部分 cur.next l1 if l1 else l2 return dummy.next过程演示Java解法仅说明归并代码示例public ListNode sortList(ListNode head) { // 递归终止条件链表为空或只有一个节点 if (head null || head.next null) { return head; } // 找到链表的中点 ListNode mid findMiddle(head); ListNode rightHead mid.next; // 右半部分的头节点 mid.next null; // 断开链表 // 递归排序左半部分和右半部分 ListNode left sortList(head); ListNode right sortList(rightHead); // 合并两个有序链表 return mergeTwoLists(left, right); } // 找到链表的中点快慢指针法 private ListNode findMiddle(ListNode head) { ListNode slow head; ListNode fast head.next; // fast 从 head.next 开始确保 slow 指向中点或左中点 while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } return slow; } // 合并两个有序链表 private ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy new ListNode(-1); // 虚拟头节点 ListNode curr dummy; while (l1 ! null l2 ! null) { if (l1.val l2.val) { curr.next l1; l1 l1.next; } else { curr.next l2; l2 l2.next; } curr curr.next; } // 将剩余的链表接上 if (l1 ! null) { curr.next l1; } if (l2 ! null) { curr.next l2; } return dummy.next; }改为PythonC解法同Java代码示例struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; class Solution { public: ListNode* sortList(ListNode* head) { // 递归终止条件 if (head nullptr || head-next nullptr) { return head; } // 找中点 ListNode* mid findMiddle(head); ListNode* rightHead mid-next; mid-next nullptr; // 递归排序左右两部分 ListNode* left sortList(head); ListNode* right sortList(rightHead); // 合并有序链表 return mergeTwoLists(left, right); } private: // 快慢指针找左中点 ListNode* findMiddle(ListNode* head) { ListNode* slow head; ListNode* fast head-next; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; } return slow; } // 合并两个有序链表使用三目运算符简化收尾 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(-1); ListNode* curr dummy; while (l1 ! nullptr l2 ! nullptr) { if (l1-val l2-val) { curr-next l1; l1 l1-next; } else { curr-next l2; l2 l2-next; } curr curr-next; } // C 同样支持三目运算符 curr-next l1 ? l1 : l2; return dummy.next; } };注意Java的三目运算不能省略nullJava 中对象引用不能直接当成布尔条件
