Sorting LinkedList

Question

I cannot figure out where is something I'm missing in the code. Why it only sorts once and puts 50 at last and rest of element are as it was before. Here is my Code.

//TO SORT THE LINKED LIST
  static Node sorted(Node head){
      
      Node temp1 = head;
      Node temp2 = head;
      while(temp1 != null){
          while(temp2 != null){
              if(temp2.data > temp2.next.data){
                  int temp = temp2.data;
                  temp2.data = temp2.next.data;
                  temp2.next.data = temp;
              }
              temp2 = temp2.next;
          }
          temp1 = temp1.next;
      }
      return head;
  }

Answer 1

There are two issues in your code:

1. temp2 should restart from the beginning of the list in every iteration of the outer loop.
2. temp2.next will eventually be null when temp2.next.data is evaluated. You need to exit the inner loop when you arrive at the last node, not when you are past the last node. So the while condition should be temp2.next != null

With those corrections it will work:

    static Node sorted(Node head){
        Node temp1 = head;
        while (temp1 != null) {
            Node temp2 = head;
            while (temp2.next != null) {
                if (temp2.data > temp2.next.data){
                    int temp = temp2.data;
                    temp2.data = temp2.next.data;
                    temp2.next.data = temp;
                }
                temp2 = temp2.next;
            }
            temp1 = temp1.next;
        }
        return head;
    }

Now, there are still several remarks to make:

1. You should check whether it is acceptable to swap the data of the nodes, instead of swapping (and rewiring) the nodes themselves. If the caller of the method has references to individual nodes in the list, they may not expect that these nodes will have different values after the list has been sorted. This may come as an unpleasant surprise. Many code challenges will require that you do not modify the data member of nodes, but only their next properties.

2. You chose bubble sort as your sorting algorithm. This is not a very efficient sorting algorithm, and even this implementation of it could be improved by stopping the inner loop sooner -- knowing that the tail of the list gets sorted gradually, and the outer loop could also exit sooner when it is found that no more swaps were performed. But you'll have a more efficient algorithm when you go for merge sort or quick sort.

3. The name of the function should be sort, since it modifies the given list. The name sorted would suggest that it doesn't modify the given list, but produces a new list that is the sorted version of it.

4. temp1 and temp2 are not descriptive variable names. Think of more descriptive names.

5. You wrote "Why it only sorts once and puts 50 at last and rest of element are as it was before.", but the given code does not have that behaviour: it runs into an exception.