Explanation with invariance

  • 0

    separate the list into 3 parts:

    1. [1, iter = m-1], before reversed part
    2. [m, n], reversed part
    3. [n, len], rest part
    |--------------| |-----------|  |-------------|
    1            m-1  m          n  n+1           len
                iter           pre  rest

    According to the conditions, the 2nd part will never be empty.
    However, the 1st part and the 3rd could be empty.

    During the reversing phase, the invariance holds:

    After every iteration, the pre is the head of the reversed list, and rest is the head of the unreversed list.

    The 3rd part could be empty means that rest could be null. Since the 3rd part will only being linked but not to link others, the operation will always safe.

    But we need to introduce a way to indicate that the 1st part is empty. A dummy will do.

Log in to reply

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