爲什麼我不能只用node = node.next遍歷鏈表？

Question

我目前正在破解編碼訪問問題（2.4），我應該圍繞一個值x對鏈表進行分區，使得所有小於x的節點在所有節點大於或等於x之前出現。然而，我很困惑，爲什麼需要一個臨時變量「next」，爲什麼node.next在它之下。爲什麼我不能在while循環結束時執行node = node.next？

我只是在創建兩個鏈接列表之前和之後，並將正確的值放入每個列表後合併在一起。

public static Node partition(Node node, int x) { 
    Node beforeStart = null; 
    Node beforeEnd = null; 
    Node afterStart = null; 
    Node afterEnd = null; 

    /* Partition list */ 
    while (node != null) { 
     Node next = node.next; 
     node.next = null; 
     if (node.data < x) { 
      if (beforeStart == null) { 
       beforeStart = node; 
       beforeEnd = beforeStart; 
      } else { 
       beforeEnd.next = node; 
       beforeEnd = beforeEnd.next; 
      } 
     } else { 
      if (afterStart == null) { 
       afterStart = node; 
       afterEnd = afterStart; 
      } else { 
       afterEnd.next = node; 
       afterEnd = afterEnd.next; 
      } 
     } 
     node = next;  
    } 

    /* Merge before list and after list */ 
    if (beforeStart == null) { 
     return afterStart; 
    } 

    beforeEnd.next = afterStart; 
    return beforeStart; 
} 

Answer 1

爲什麼我不能只是做點= node.next在while循環的結束？

可以這樣做。在完成分區之後，對於每個列表，您需要將最後一個節點的下一個指針設置爲NULL。這隻需要兩行代碼。

示例代碼使用next = node.next和node.next = NULL在分區過程中終止每個列表，但在這種情況下不需要，因爲列表不需要NULL終止符，直到分區過程完成。

Answer 2

問題中的循環從原始列表的開頭刪除節點，並將它們追加到之前的列表或後續列表中，直到原始列表爲空。然後它連接前後列表。

這很容易解釋和易於理解。

可以毫不臨時next完成或在每次迭代歸零了node.next，但隨後上面的描述將不再適用 - 節點不會從原來的名單中刪除在每次迭代，列表之前和之後列表不會僅包含適當的節點，您對它們執行的操作不是「追加」，並且節點甚至會出現在多個列表中一段時間​​。

您的算法會突然變得難以描述和理解。這在軟件開發中是一件壞事，在編程面試中是一件壞事。