create a circular loop in a linear list

Asked 1 years ago, Updated 1 years ago, 325 views

I have a question about how to solve the LeetCode problem below.
https://leetcode.com/problems/partition-list/description/

As a solution to the above problem, we refer to the following:
https://leetcode.com/problems/partition-list/solutions/29174/python-concise-solution-with-dummy-nodes/?orderBy=most_votes&languageTags=python

def partition(self, head, x):
    h1 = l1 = ListNode(0)
    h2 = l2 = ListNode(0)
    while head:
        if head.val<x:
            l1.next=head
            l1 = l1.next
        else:
            l2.next=head
            l2 = l2.next
        head=head.next
    l2.next = None
    l1.next = h2.next
    return1.next

If you comment out l2.next=None immediately after the while loop of the above code, the return value becomes a circular loop, but I don't know why.
For example,

head=[1,4,3,2,5,2], x=3

returns an infinite list, such as 1, 2, 4, 3, 5, 2, 4, 3, 5, 2, 4, 4, 3, 5, 5, 4, 4, 4, 3, 4, 3, 5, 2, 4, 3, 5, 2, 4 ...
l2.next=None Why does a circular loop occur without it?

python

2023-01-25 07:11

1 Answers

At the end of the while loop, l1 points to the last val=2 node.
On the other hand, l2 refers to the last two val=5 nodes.
This next, or l2.next, refers to the last val=2 node, or l1.

After the while loop ends, l1 connects to h2.next (the first node with val greater than or equal to three), so if l2 remains connected to l1, it loops.


2023-01-25 07:27

If you have any answers or tips


© 2024 OneMinuteCode. All rights reserved.