Leetcode discuss: 328 Odd Even Linked List

Here is the link.

C# LinkedList challenge

July 14, 2020

Introduction

328. Odd Even Linked List

It is my mock interview second algorithm. I came cross the time limit exceeded bug, so I tried to fix the issue.

To simplify the maintenance of linked list, break the node's next, set it null first; Afterwards, process node to become one node in odd linked list or even linked list.

Argue that it is a good habit to keep the rule. It helps to prevent TLE error or deadloop issue.

Will add a case study why it is important to do that.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode OddEvenList(ListNode head) {
        if(head == null)
            return null;        
        
        var dummyHeadOdd = new ListNode();
        var dummyHeadEven = new ListNode(); 
        var startOdd = dummyHeadOdd;
        var startEven = dummyHeadEven;
        var lastNodeOdd = head;
        int count = 1;
        while(head != null)
        {
            var reserved = head.next; // caught by online judge - time limit exceeded
            
            head.next = null; // caught by online judge - time limit exceeded 
            
            var isOdd = count % 2 == 1; 
            if(isOdd)
            {
                startOdd.next = head;
                startOdd = startOdd.next; 
                
                // keep refreshing
                lastNodeOdd = head;
            }
            else 
            {
                startEven.next = head;
                startEven = startEven.next; 
            }                        
            
            // next iteration
            head = reserved;
            count++;
        }
        
        lastNodeOdd.next = dummyHeadEven.next;         
        
        return dummyHeadOdd.next; 
    }
}