(Python) Singly LinkedList - Leetcode

Question

I am working on this Leetcode problem https://leetcode.com/problems/odd-even-linked-list/. I already tried to debug the program with the debugging tool and found the bug in my code but I don't really understand the bug and I don't really know how to fix it. The bug came from this line: odd_head.next = even_head Thanks for your help!

The problem is: Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

For example:
Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL

Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL

def oddEvenList(self, head):
    odd_head = head
    even_head = head.next

    while(odd_head.next and odd_head.next.next):
        temp = odd_head.next.next
        odd_head.next = temp
        odd_head = temp

    odd_head.next = even_head # BUG ON THIS LINE

    while(even_head.next and even_head.next.next):
        temp = even_head.next.next
        even_head.next = temp
        even_head = temp

    return odd_head

Dipen Dadhaniya · Accepted Answer · 2019-10-09 09:54:12Z

2

Consider this list: 2->1->3->5->6->4->7->NULL

When your code reaches:

odd_head.next = even_head

Links will be:

2->3
3->6
6->7
7->NULL

1->3
5->6
4->7

even_head.next will be 3

even_head.next.next will be 6 not 5 (THIS IS WRONG.)

The reason is that the links are changed in the first while loop! Hence, from here everything starts getting wrong.

Out of many possible solutions, one simple solution:

def oddEvenList(self, head):
    if not head:
        return head

    odd_head = head
    even_head_copy = even_head = head.next

    while odd_head and even_head and even_head.next:
        odd_head.next = even_head.next
        odd_head = odd_head.next

        even_head.next = odd_head.next
        even_head = even_head.next

    odd_head.next = even_head_copy
    return head

edited Oct 9, 2019 at 9:54

answered Oct 9, 2019 at 9:48

Dipen Dadhaniya

4,6602 gold badges19 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

curiousP Over a year ago

Thank you! Now it make senses why it gets stuck in the while loop.

Mr.ByN · Accepted Answer · 2019-10-09 09:49:12Z

A proper solution would be:

class Solution:
    def oddEvenList(self, head):
        try:
            odd = head
            even_head=head.next
            even = head.next
            cur=even.next
        except:
            return head
        try:
            while cur!=None:
                odd.next=cur
                odd=odd.next
                even.next=cur.next
                even=even.next
                cur=cur.next.next
                print(even.val)
        except:
            pass
        odd.next=even_head
        return head

The first try block is to initialize the variable and handle the corner case where the list have less than 2 elements. The second try block looping through the list.

Collectives™ on Stack Overflow

(Python) Singly LinkedList - Leetcode

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related