插入排序的链接列表

Question

我试图实现一个有插入，删除，并检查整数是否存在方法的排序链接列表，我目前无法理解为什么我的插入方法工作不正确。它将整数插入链表中，但它们向后排序，我尝试过移动条件，但它不能按照它的方式工作。

void insert(int x){ 
    LinkedList newLink = new LinkedList(x); 
    if (front == null) { 
     front = newLink; 
    } else if (x > front.x){ 
     newLink.next = front; 
     front = newLink; 
    } else { 
     LinkedList current = front.next; 
     LinkedList before = front; 
     while (current != null){ 
      if (x < front.x) { 
       before = current; 
       current = current.next; 
      } 
      newLink.next = before.next; 
      before.next = newLink; 
     } 
    } 
} 

Answer 1

我认为这将解决您的问题，再加上，我添加了一些意见让你了解我的变化在你的代码：

void insert(int x) { 
    LinkedList newLink = new LinkedList(x); 
    if (front == null) { 
     front = newLink; 
     // insert in head if x is lower than the head 
    } else if (x <= front.x) { 
     newLink.next = front; 
     front = newLink; 
    } else { 
     // find the first node which value is lower than x (or the tail) 
     LinkedList current; 
     for (current = front; current.next != null && x >= current.next.x ; current = current.next); 
     // to remove duplicates 
     if (x != current.x) { 
      newLink.next = current.next; 
      current.next = newLink; 
     } 
    } 
} 

Answer 2

else if (x > front.x){ 
    newLink.next = front; 
    front = newLink; 
} 

如果新的链接比前面更大，使新节点front节点，它的下一个节点设置为最近前面。您按逆序排序顺序插入列表的前面。

if (x < front.x) { 
    before = current; 
    current = current.next; 
} 

你总是比较的front节点为好，不是你的current节点。

Answer 3

附上我的实现。请使用和修改您的需求。

注意！这个实现将会降低相同的值！

/****************************************************************** 
* Adds the given string to the sorted list. If the string already 
* is in the list, then the list will not be modified. 
* 
* @param list The sorted list of strings 
* @param str The string to be inserted if not there already 
* @return Returns true if the list has changed otherwise false 
*/ 
public static boolean 
add2SortedList(List<String> list, String str) { 
    int res = 0; 

    //--- Loop through list from end to front 
    for (int i = list.size() - 1; i >= 0 ; i--) { 

     //--- Compare to current entry 
     res = str.compareTo(list.get(i)); 

     //--- Already in list => return 
     if (res == 0) 
      return false; 

     //--- Bigger than current one => insert after 
     if (res > 0) { 
      list.add(i + 1, str); 
      return true; 
     } 
    } 

    //--- Insert at head of list 
    list.add(0, str); 
    return true; 
} 


/****************************************************************** 
* Adds the given value to the sorted list if its not already there. 
* 
* @param list the sorted list of values 
* @param value the value to be inserted if not there already 
* @return returns true when value was added, else false 
*/ 
public static boolean 
add2SortedSet(List<Integer> list, Integer value) 
{ 
    int size = list.size(); 
    for (int i = 0 ; i < size ; i++) 
    { 
     int res = value.compareTo (list.get(i)); 

     //----- Insert before this element 
     if (res < 0) { 
      list.add(i, value); 
      return true ; 
     } 

     //----- New element already in list 
     if (res == 0) 
      return false ; 
    } 

    //----- Append to end of list 
    list.add (value); 
    return true ; 
} 

Answer 4

默认方式在一个LinkedList插入：

LinkedList<Integer> myList = new LinkedList<>(); 

myList.add(238); 
myList.add(7); 
..   
Collections.sort(myList); 

http://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html

了不同的排序方式使用接口可比