可以先计算每个嵌套链表内索引值之和,再利用快速排序算法对链表进行排序。具体实现代码如下:
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public ListNode sortLinkedListOfLinkedList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode pivot = head;
ListNode curr = head.next;
ListNode left = null;
ListNode right = null;
ListNode temp = null;
while (curr != null) {
if (getSum(curr) < getSum(pivot)) {
if (left == null) {
left = curr;
temp = left;
} else {
temp.next = curr;
temp = temp.next;
}
} else {
if (right == null) {
right = curr;
temp = right;
} else {
temp.next = curr;
temp = temp.next;
}
}
curr = curr.next;
}
if (temp != null) {
temp.next = null;
}
ListNode leftSorted = sortLinkedListOfLinkedList(left);
ListNode rightSorted = sortLinkedListOfLinkedList(right);
if (leftSorted == null) {
return pivot;
} else {
temp = leftSorted;
while (temp.next != null) {
temp = temp.next;
}
temp.next = pivot;
pivot.next = rightSorted;
return leftSorted;
}
}
private int getSum(ListNode head) {
int sum = 0;
ListNode curr = head;
while (curr != null) {
sum += curr.val;
curr = curr.next;
}
return sum;
}