93554


以下のLeetCodeの問題の解法について質問です。  
<https://leetcode.com/problems/partition-list/description/>

上記問題の解法として以下を参考にしております。  
[https://leetcode.com/problems/partition-list/solutions/29174/python-concise-
solution-with-dummy-
nodes/?orderBy=most_votes&languageTags=python](https://leetcode.com/problems/partition-
list/solutions/29174/python-concise-solution-with-dummy-
nodes/?orderBy=most_votes&languageTags=python)

[code]

    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
        return h1.next
    
[/code]

上記コードのwhileループ直後の`l2.next = None`をコメントアウトすると戻り値が循環ループになってしまうのですが、その理由がわかりません。  
例えば、例題

[code]

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

では、1, 2, 2, 4, 3, 5, 2, 4, 3, 5, 2, 4, 3, 5, 2, 4, 3, 5, 2,
4...のような無限に続くリストが返ってきます。  
`l2.next = None`なしでは循環ループが発生する理由を教えてください。


CC BY-SA 4.0
2023-01-25T00:09:47.543
93553
2023-01-25T01:15:05.013
56454
question
python
線形リストで循環ループができてしまう


whileループ終了時、`l1`は一番最後の`val=2`のノードを指しています。  
一方で`l2`は最後から2番めの`val=5`のノードを指しています  
この`val=5`の`next`、すなわち`l2.next`は一番最後の`val=2`のノードつまり`l1`を指しています。

whileループ終了後、`l1`は`h2.next`(`val`が3以上の一番最初のノード)につなぎますので、`l2`が`l1`につながったままだとループします。


CC BY-SA 4.0
2023-01-25T01:15:05.013
93554
2023-01-25T01:15:05.013
13127
93553
answer