A strange problem ?


  • 0

    I encounter a very strange problem when solved this problem via merge sort.
    my code:

    public class Solution {
    	public ListNode sortList(ListNode head) {
    		if (head == null || head.next == null) {
    			return head;
    		}
    		// Recursive case. First, divide the list into equal-sized sublists
    		// consisting of the first half and second half of the list.
    		ListNode slow = head;
    		ListNode fast = head;
    		ListNode prev = null;
    		while (fast != null && fast.next != null) {
    			prev = slow;
    			slow = slow.next;
    			fast = fast.next.next;
    		}
    		prev.next = null;
    		// Recursively sort both sublists.
    		slow = sortList(head);
    		fast = sortList(slow);
    		return merge(slow, fast);
    	}
    
    	private ListNode merge(ListNode left, ListNode right) {
    		ListNode dummy = new ListNode(-1);
    		ListNode traverse = dummy;
    		while (left != null && right != null) {
    			if (left.val < right.val) {
    				traverse.next = left;
    				left = left.next;
    			} else {
    				traverse.next = right;
    				right = right.next;
    			}
    			traverse = traverse.next;
    		}
    		while(left != null){
    			traverse.next = left;
    			traverse = traverse.next;
                            System.out.println(left.next == left);
    			left = left.next;
    		}
    		while(right != null){
    			traverse.next = right;
    			traverse = traverse.next;
    			right = right.next;
    		}
    		
    		return dummy.next;
    	}
    }
    

    test case is [2, 1]
    and the problem is

    System.out.println(left.next == left);
    

    I found my solution is endless loop because left.next == left
    why????


  • 0

    who can explain this problem?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.