Simple Java solutions in two ways


  • 0
    L

    Of course, there are multiple ways. However, I found these two ways to be commonly coming to my mind. The first pattern looks clumsy where you keep even and odd counter and then merge them together. The caveat is the edge case when it is odd-numbered and the even ptr may still keep reference to the next odd pointer. So that should be cleaned up before merge. Here is the code for that:

        public ListNode oddEvenList(ListNode head) {
         if (head == null) {
          return null;
         }
         ListNode oddHead = new ListNode(0);
         ListNode oddIt = oddHead;
         ListNode evenHead = new ListNode(0);
         ListNode evenIt = evenHead;
         int toggle = 1;
         while (head != null) {
          if ((toggle ^ 0) == 1) {
           oddIt.next = head;
           oddIt = oddIt.next;
          } else {
           evenIt.next = head;
           evenIt = evenIt.next;
          }
          head = head.next;
          toggle ^= 1;
         }
         evenIt.next = null;
         oddIt.next = evenHead.next;
         return oddHead.next;
        }
    

    Pay attention to the evenIt.next=null. It is required since the last even ptr will hold its next pointer to the last odd list. Rest is simple. The approach below is simple where in one iteration you do both work. Just make sure that you could assign both pointers in that iteration; just set null otherwise.

        public ListNode oddEvenList(ListNode head) {
            if (head == null){
              return null;
            }
            ListNode oddHead = new ListNode(0);
            ListNode oddIt = oddHead;
            ListNode evenHead = new ListNode(0);
            ListNode evenIt = evenHead;    
            while (head != null) {
                oddIt.next = head;
                evenIt.next = head.next;
                oddIt = oddIt.next;
                evenIt = evenIt.next;
                if(head.next!=null) {
                    head = head.next.next;
                }
                else {
                    head = null;
                }
            }
            oddIt.next = evenHead.next;
            return oddHead.next;
        }
    

Log in to reply
 

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