【归并】BM12.单链表的排序

思路求解代码ListNodemerge(ListNodepHead1,ListNodepHead2){// 任一链表为空直接返回另一链表if(pHead1null){returnpHead2;}if(pHead2null){returnpHead1;}// 虚拟节点简化合并后链表头节点的处理ListNodedummynewListNode(0);ListNodeheaddummy;// 结果链表的当前指针用于挂载节点while(pHead1!nullpHead2!null){if(pHead1.valpHead2.val){head.nextpHead1;pHead1pHead1.next;}else{head.nextpHead2;pHead2pHead2.next;}headhead.next;// 结果指针后移}// 拼接剩余节点if(pHead1!null){head.nextpHead1;}else{head.nextpHead2;}// 返回合并后的链表returndummy.next;}publicListNodesortInList(ListNodehead){// 空链表/单节点链表直接返回if(headnull||head.nextnull){returnhead;}ListNodelefthead;// 慢指针前驱用于断开链表ListNodemidhead.next;// 慢指针最终指向中点ListNoderighthead.next.next;// 快指针步长2// 持续移动指针直到快指针到末尾while(right!nullright.next!null){leftleft.next;// 慢指针前驱后移midmid.next;// 慢指针后移步长1rightright.next.next;// 快指针后移步长2}left.nextnull;// 断开链表拆分为「head→left」和「mid→末尾」两段// 递归排序两段链表再合并结果returnmerge(sortInList(head),sortInList(mid));}