Question I do not understand!!!!!!!!!!!! WHY need .next=null???????????


  • 0
    J

    /**

    • Definition for singly-linked list.

    • public class ListNode {

    • int val;
      
    • ListNode next;
      
    • ListNode(int x) { val = x; }
      
    • }
      */
      public class Solution {
      public void reorderList(ListNode head) {
      if(head==null || head.next == null) return;

       ListNode first,second,truehead;
       first = second = truehead = head;
       
       while(second.next!=null && second.next.next!=null) 
       {
           first = first.next;
           second = second.next.next;
       }
       
       second = first.next;
       
       first.next = null;//?????????????????????????????????????????????????????????????? why????????????????
       
       first = truehead;
       
       second = reverse(second);
      
        //merge second and first
        while(second != null && first != null)
        {
               ListNode temp_second = second.next;
               ListNode temp_first = first.next;
                
                first.next = second;
                second.next = temp_first;
    
                first = temp_first;
                second = temp_second;
        }
        
       
    }
    
    public ListNode reverse(ListNode head)
    {
        if(head == null || head.next == null) return head;
        
        ListNode pre,middle,last;
        pre = null;
        middle = head;
       // last = head.next.next;
        
        while(middle != null)
        {
            last = middle.next;
            middle.next = pre;
            //last.next = middle;
            
            pre = middle;
            middle = last;
        }
        
        return pre;
    }
    

    }

    As I show, the code first.next = null; is required. Or it will report the exceed the memory limit!!!
    WHY???


  • 0
    Y

    because if you dont separate the second half from first half before you reverse it, you will create a cycle in your final linked list.


  • 0
    J

    Oh, that is it. Thanks


Log in to reply
 

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