Odd Even Linked List


  • 1

    Click here to see the full article post


  • 0
    F

    an easy understand idea,good


  • 0
    P

    I am doing something similar albeit with more variables. My solution works for all inputs except 1->2->3 for which I am getting a run time error. Can someone please help me out why I am getting a run time error for an input of size 3?

      ListNode *even, *firsteven, *odd, *curr;
      
      if(head == NULL)
          return NULL;
          
      odd = head;
      even = head;
      curr = head;
      
      if(head->next) {
          even = even->next;
          firsteven = head->next;
      }
      else return head;
      
      if(head->next->next)
          curr = head->next->next;
      else return head;
    
      while(curr) {
          even->next = curr->next;
          curr->next = NULL;
          odd->next = curr;
          curr->next = firsteven;
          odd = odd->next;
          even = even->next;
          even->next ? curr = even->next : curr = NULL;
      }
      
      return head;
    

  • -1
    T

    Wrong test cases.


  • -1
    T

    Forgot to clarify. Here:

    Input:
    [2,1,4,3,6,5,7,8]
    Expected:
    [2,4,6,7,1,3,5,8]


  • 0
    Z

    @piy9 It has been some time since you posted, and I don't know if you have found out the answer or not. But anyway, I will share my thoughts here.

    I got similar error in my first few submits: if the whole list has odd number nodes in total, like 3, 5, 7 and etc., I will get run time error.

    It turned out to be that I have to specifically make my even list's last node point to NULL. Otherwise it would generate a ring list. Try it. I guess it would solve your problem too.


  • 0
    S

    This is what I tried, Iterate list with current node with a loop counter. if loop counter is even then add current node to evenlist otherwise add to oddlist.

    public ListNode OddEvenList(ListNode head)
    {
    if(head == null || head.next == null)
    return head;

        ListNode currNode = head; 
        ListNode oddList  = currNode;
        ListNode evenList = currNode.next;
        ListNode evenHead = evenList;
        
        currNode = currNode.next.next;
        
        int lpCnt = 3;
        
        while(currNode != null)
        {
            if(lpCnt % 2 == 0)
            {
               evenList.next = currNode;
               evenList = evenList.next;
            }
            else
            {
               oddList.next = currNode;
               oddList = oddList.next;
            }
            
            currNode = currNode.next;
            ++lpCnt;
        }
    
        if (evenList != null)
            evenList.next = null;
    
        if(oddList != null)
            oddList.next = evenHead;
            
        return head;   
    

    }


  • 0
    Y

    In Ruby, here's what that looks like

    def odd_even_list(head)
      return head if head.nil? || head.next.nil? # We need at least 2 nodes
      
      odd_tail = head
      current = head.next
      while current && current.next do
        next_node = current.next
    
        current.next = next_node.next # skip over odd element
        even_head = odd_tail.next # beginning of even chain
    
        odd_tail.next = next_node # link to previous node
        next_node.next = even_head # link to next node
    
        odd_tail = next_node # update odd_tail
        
        current = current.next # move forward
      end
      
      head
    end
    

  • 0
    R
    This post is deleted!

  • 0
    P

    Was getting a timelimit error on the [1, 2, 3] case even though the first test case passed. I added a null to the end of the returned list and it solved the problem. It might be some test cases expect a null to be the last node whereas the first test case didn't. The example in the instructions show a null as the last linked list so you want to make sure to add that. It hung me up for a while.


  • 0

    My slightly different solution here, illustrated and explained. My approach does not rely on building a separate list on the side, but rather just relies on deleting and inserting, not that they are so much different in essence though.

    Admittedly, I do think this solution is more elegant than mine.

    In


  • 0
    L

    The even list has n/2 nodes. Why does your solution has O(1) space complexity? Is it just because you created a new evenHead pointer and did not create any new listNodes in memory?


Log in to reply
 

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