My ac java code


  • 5
    T

    public ListNode partition(ListNode head, int x) {

    	ListNode firstHead = new ListNode(0);
    	firstHead.next = head;
    	ListNode secondHead = new ListNode(x);
    
    	
    	ListNode first = firstHead;
    	ListNode second = secondHead;
    	ListNode curNode = head;
    	while(curNode!=null){
    		ListNode tmp = curNode.next;
    		if(curNode.val<x){
    			
    			first.next = curNode;
    			first = curNode; 
    		}else{
    			second.next = curNode;
    			second = curNode;
    			second.next = null;// important
    		}
    		curNode = tmp;
    	}
    	first.next = secondHead.next;
    	return firstHead.next;
    }

  • 0

    second.next = null;// important This is exactly statement I missed...

    Could you please explain why we need to cut the link in the second half but do not have to in the first half? I am trying to find the key to void cycle in linked list.


  • 0
    S

    I could not understand what you mean by second and first half.Could you please explain me that more.

    Here we do not need to change any elements order which are greater than or equal to x.Their order should be intact.But the elements which are < x has to be come before x hence all those should be group in one place before x.Hence it will be easier if we cut the link when ever we come across an element >= x (we do not want to change these elements).Hence the end element of this set should be null.because all these will be come after those elements < x. Please correct me if I am wrong or it is irrelevant to your question.


  • 1
    F

    Otherwise, you will return a linkedlist with loop. You do not need to do for the first half, since it's next is pointing to the second half.


  • 0
    A

    can move below line out of while loop to save some time
    second.next = null;// important


Log in to reply
 

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