147. Insertion Sort List

请教一下，为什么ListNode pre = res;这行必须放在大while loop之内

1. public ListNode insertionSortList(ListNode head) {
   
2.         if (head == null || head.next == null) return head;
   
3.         ListNode res = new ListNode(-1);
   
4.         ListNode cur = head;
   
5.         while(cur != null){
   
6.             ListNode pre = res;
   
7.             ListNode next = cur.next;
   
8.             while(pre.next != null && pre.next.val <= cur.val){
   
9.                 pre = pre.next;
   
10.             }
    
11.             //otherwise insertion (swap)
    
12.             cur.next = pre.next;
    
13.             pre.next = cur;
    
14.             cur = next;
    
15.         }
    
16.         return res.next;
    
17.     }

复制代码

ListNode pre = res; 這一行的意義是，每次要 insert cur 到 res list 中，都必須從 res list 的頭開始比較。你當然也可以在迴圈外宣告 pre，但每一圈還是得做 pre = res;

1. /**
   
2. * Definition for singly-linked list.
   
3. * public class ListNode {
   
4. *     int val;
   
5. *     ListNode next;
   
6. *     ListNode(int x) { val = x; }
   
7. * }
   
8. */
   
9. class Solution {
   
10.     public ListNode insertionSortList(ListNode head) {
    
11.         if (head == null || head.next == null) return head;
    
12.         ListNode res = new ListNode(-1);
    
13.         ListNode cur = head;
    
14.         ListNode pre;
    
15.         
    
16.         while(cur != null){
    
17.             pre = res;
    
18.             ListNode next = cur.next;
    
19.             
    
20.             while(pre.next != null && pre.next.val <= cur.val){
    
21.                 pre = pre.next;
    
22.             }
    
23.             
    
24.             //otherwise insertion (swap)
    
25.             cur.next = pre.next;
    
26.             pre.next = cur;
    
27.             cur = next;
    
28.         }
    
29.         return res.next;
    
30.     }
    
31. }

复制代码

不確定這有沒有回答到你的問題。

PoJen 发表于 2020-4-9 03:19
ListNode pre = res; 這一行的意義是，每次要 insert cur 到 res list 中，都必須從 res list 的頭開始比較 ...

谢谢解答！还有一点不明白的是，为什么每次while循环都得从res list的头开始比较，而不是接着上一层的pre进行比较

用下面提供的這個範例；2 -> 4 -> 1，假設每次都接著上一次迴圈的 pre 進行比較，就會得到下面的錯誤結果：



你也可以自己照這個範例走過一遍，就能想明白，如果你照著上一層的 pre 繼續比較，你永遠也沒辦法把 1 放到 2 的前面。

我有上 leetcode 實測過上面的範例，注意 pre = res 在迴圈外：

好详细的解释，太感谢了！好想给你多加些米，可惜每次只能加一颗

哈謝謝樓主，沒關係，剛好有點空，舉手之勞

hello~ 之前看帖子，你好像有一起报名udacity 的 java developer 课程。 如果有的话，可以分享下吗？我可以分担下学费。官网报不了了，谢谢🙏

Gullgosse 发表于 2020-5-1 13:51
hello~ 之前看帖子，你好像有一起报名udacity 的 java developer 课程。 如果有的话，可以分享下吗？我可以 ...

Hello, 我最后也没上那个课程，课程一直处于升级状态，没开课。