CODEWITHSUNDEEP
pythonlinked-list
curiousP
curiousP

Reputation: 69

(Python) Singly LinkedList - Leetcode

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

Upvotes: 1

Views: 483

Answers (2)

Dipen Dadhaniya
Dipen Dadhaniya

Reputation: 4630

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

Upvotes: 2

Mr.ByN
Mr.ByN

Reputation: 56

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.

Upvotes: 1

Related Questions