如何排序鏈接列表並刪除任何重複

Question

我有一個方法，接受兩個鏈接列表並打印出一個新的鏈接列表，這是兩個來電列表組合。我想知道如何排序最終列表並刪除重複項。任何幫助將不勝感激！

這裏是我的代碼：

public static IntNode method(IntNode head1, IntNode head2){ 

    // create a new list that will hold the two incoming lists 
    IntNode new_head = new IntNode(0, null); 
    IntNode new_node = new_head; 

    for(; head1 != null; head1 = head1.link) { 
     new_node.link = new IntNode(head1.data, null); 
     new_node = new_node.link; 
    } 

    for(; head2 != null; head2 = head2.link) { 
     new_node.link = new IntNode(head2.data, null); 
     new_node = new_node.link; 
    } 

    return new_head.link; 
} 

Answer 1

我做的第一件事是寫一個方法，如果你不已經有一個，插入一個節點到一個列表：

public static IntNode insertNode(IntNode head, IntNode node) 
{ 
    node.link = null; 
    if (head == null) { 
     return node; 
    } 
    IntNode root = head; 
    while (root.link != null) { 
     root = root.link; 
    } 
    root.link = node; 
    return head; 
} 

然後，你的合併和刪除重複例程將是這樣的：

public static IntNode method(IntNode head1, IntNode head2) 
{ 

    List<Integer> sort = new ArrayList<>(); 

    for (IntNode n = head1; n != null; n = n.link) { 
     sort.add(n.data); 
    } 
    for (IntNode n = head2; n != null; n = n.link) { 
     sort.add(n.data); 
    } 

    Collections.sort(sort); 

    // run though sorted list, removing adjacent duplicates 
    for (int i = 0; i < sort.size(); ++i) { 
     if (i > 0 && sort.get(i) == sort.get(i - 1)) { 
      sort.remove(i); 
     } 
    } 

    // Now put the sorted, unduplicated numbers into a new list of IntNodes 
    IntNode new_head = null; 
    for (int data : sort) { 
     IntNode newNode = new IntNode(data, null); 
     new_head = insertNode(new_head, newNode); 
    } 
    return new_head; 
}