分區單鏈表

Question

我這樣做exercice：

編寫代碼分區鏈表繞x的值，以使所有節點小於X來之前的所有節點大於或等於x。輸入示例：3→5→8→5→10→2→1輸出：3→1→2→10→5→5→8

我發現很難找到單鏈表的解決方案（由我自己創建，而不是使用庫），我想知道在我的代碼中是否有不必要的代碼塊，並且有沒有辦法避免放入兩個列表然後合併？因爲它似乎有非常緩慢的表現。

public CustomLinkedList partition(CustomLinkedList list, int x) { 
    CustomLinkedList beforeL = new CustomLinkedList(); 
    CustomLinkedList afterL = new CustomLinkedList(); 
    LinkedListNode current = list.getHead(); 
    while (current != null) { 
     if (current.getData() < x) { 
      addToLinkedList(beforeL, current.getData()); 
     } else { 
      addToLinkedList(afterL, current.getData()); 
     } 
     // increment current 
     current = current.getNext(); 
    } 
    if (beforeL.getHead() == null) 
     return afterL; 
    mergeLinkedLists(beforeL, afterL); 
    return beforeL; 
} 

public void addToLinkedList(CustomLinkedList list, int value) { 
    LinkedListNode newEnd = new LinkedListNode(value); 
    LinkedListNode cur = list.getHead(); 
    if (cur == null) 
     list.setHead(newEnd); 
    else { 
     while (cur.getNext() != null) { 
      cur = cur.getNext(); 
     } 
     cur.setNext(newEnd); 
     cur = newEnd; 
    } 
} 

public void mergeLinkedLists(CustomLinkedList list1, CustomLinkedList list2) { 
    LinkedListNode start = list1.getHead(); 
    LinkedListNode prev = null; 
    while (start != null) { 
     prev = start; 
     start = start.getNext();   
    } 
    prev.setNext(list2.getHead()); 
} 

CustumLinkedList包含兩個屬性：-LinkedListNode其是頭和一個int它的大小。 一個LinkedListNode包含兩個屬性：一個LinkedListNode類型指向下一個節點和int類型之一：數據值

謝謝。

Answer 1

我認爲維護兩個列表不是問題。可以使用單個列表，但需要花費一些簡單的代價。

主要問題似乎是addToLinkedList(CustomLinkedList list, int value)方法。

它遍歷整個列表以添加一個新元素。

一種替代方法是始終在列表的前面添加元素。這也會產生一個有效的解決方案，並且運行得更快。

Answer 2

您的代碼的問題不是正如您所提到的，合併兩個列表。在這裏使用merge這個詞是錯誤的，因爲你只有連接左邊列表的尾部與右邊列表的頭部是一個常量時間操作。

真正的問題是 - 在左側或右側列表中插入一個新的元素，你是從每頭這將產生在計O(n^2)操作肯定是緩慢的時間迭代到尾。

在這裏，我寫了一個更簡單的版本，並避免每次從頭開始迭代以通過跟蹤當前尾部來插入新項目。

代碼非常簡單，而且肯定比您的代碼更快（O(n)）。讓我知道你是否需要解釋任何部分。

// I don't know how your CustomLinkedList is implemented. Here I wrote a simple LinkedList node 
public class ListNode { 
    private int val; 
    private ListNode next; 
    public ListNode(int x) { 
     val = x; 
    } 
    public int getValue() { 
     return this.val; 
    } 
    public ListNode getNext() { 
     return this.next; 
    } 
    public void setNext(ListNode next) { 
     this.next = next; 
    } 
} 

public ListNode partition(ListNode head, int x) { 

    if(head == null) return null; 

    ListNode left = null; 
    ListNode right = null; 

    ListNode iterL = left; 
    ListNode iterR = right; 

    while(iter != null) { 

     if(iter.getValue() < x) { 
      iterL = addNode(iterL, iter.getValue()); 
     } 
     else { 
      iterR = addNode(iterR, iter.getValue()); 
     } 

     iter = iter.getNext(); 
    } 

    // link up the left and right list 
    iterL.setNext(iterR); 

    return left; 
} 

public ListNode addNode(ListNode curr, int value) { 

    ListNode* newNode = new ListNode(value); 

    if(curr == null) { 
     curr = newNode; 
    } else { 
     curr.setNext(newNode); 
     curr = curr.getNext(); 
    } 

    return curr; 
} 

希望它有幫助！

Answer 3

如果您有任何數據清單，請訪問orderByX方法。 希望它能幫助你。

public class OrderByX { 
Nodes root = null; 

OrderByX() { 
    root = null; 
} 

void create(int[] array, int k) { 
    for (int i = 0; i < array.length; ++i) { 
     root = insert(root, array[i]); 
    } 
} 

Nodes insert(Nodes root, int data) { 
    if (root == null) { 
     root = new Nodes(data); 
    } else { 
     Nodes tempNew = new Nodes(data); 
     tempNew.setNext(root); 
     root = tempNew; 
    } 
    return root; 
} 

void display() { 
    Nodes tempNode = root; 
    while (tempNode != null) { 
     System.out.print(tempNode.getData() + ", "); 
     tempNode = tempNode.getNext(); 
    } 
} 

void displayOrder(Nodes root) { 
    if (root == null) { 
     return; 
    } else { 
     displayOrder(root.getNext()); 
     System.out.print(root.getData() + ", "); 
    } 

} 

Nodes orderByX(Nodes root, int x) { 
    Nodes resultNode = null; 
    Nodes lessNode = null; 
    Nodes greatNode = null; 
    Nodes midNode = null; 
    while (root != null) { 
     if (root.getData() < x) { 
      if (lessNode == null) { 
       lessNode = root; 
       root = root.getNext(); 
       lessNode.setNext(null); 
      } else { 
       Nodes temp = root.getNext(); 
       root.setNext(lessNode); 
       lessNode = root; 
       root = temp; 
      } 
     } else if (root.getData() > x) { 
      if (greatNode == null) { 
       greatNode = root; 
       root = root.getNext(); 
       greatNode.setNext(null); 
      } else { 
       Nodes temp = root.getNext(); 
       root.setNext(greatNode); 
       greatNode = root; 
       root = temp; 
      } 
     } else { 

      if (midNode == null) { 
       midNode = root; 
       root = root.getNext(); 
       midNode.setNext(null); 
      } else { 
       Nodes temp = root.getNext(); 
       root.setNext(midNode); 
       midNode = root; 
       root = temp; 
      } 

     } 
    } 
    resultNode = lessNode; 
    while (lessNode.getNext() != null) { 
     lessNode = lessNode.getNext(); 
    } 
    lessNode.setNext(midNode); 
    while (midNode.getNext() != null) { 
     midNode = midNode.getNext(); 
    } 
    midNode.setNext(greatNode); 
    return resultNode; 
} 

public static void main(String... args) { 
    int[] array = { 7, 1, 6, 2, 8 }; 
    OrderByX obj = new OrderByX(); 
    obj.create(array, 0); 
    obj.display(); 
    System.out.println(); 
    obj.displayOrder(obj.root); 
    System.out.println(); 
    obj.root = obj.orderByX(obj.root, 2); 
    obj.display(); 

} 
} 

class Nodes { 

private int data; 
private Nodes next; 

Nodes(int data) { 
    this.data = data; 
    this.next = null; 
} 

public Nodes getNext() { 
    return next; 
} 

public void setNext(Nodes next) { 
    this.next = next; 
} 

public int getData() { 
    return data; 
} 

public void setData(int data) { 
    this.data = data; 
} 

}