更改单链表中节点的顺序

Question

假设我们有一个列表 1-2-3-4-5（列表的值可以没有顺序，例如 2-4-5-3-1）；
任务是以这样的方式重新排序列表的节点（不是值）： 1-5-2-4-3.
我编写了使用 2 个临时变量和 1 个指针的函数。但问题是我不知道如何在函数中定义第二个临时指针的情况下将倒数第二个节点中的 "next" 指针设置为 "NULL" 。有没有更有效的方法来做到这一点？

void Swap(Node* begin)
{
    if (begin->next != NULL || begin->next->next != NULL)
    {
        Node temp1 = *begin; //this variable is used for iteration
        Node* temp2 = begin; //pointer to the target node
        Node prev; //get the adress of last node
        while (temp1.next != NULL)
        {
            prev = temp1;
            temp1 = *temp1.next;
        }
        prev.next->next = temp2->next;
        temp2->next = prev.next;
        Swap(prev.next->next);
    }

}

Answer 1

所以基本上你想要做的是：

N0, N1, ..., Nm -> N0, Nm, N1, Nm-1, ..., Nm/2   if m is even
                -> N0, Nm, N1, Nm-1, ..., N(m-1/2), N(m+1/2)

您也许可以从 i in (m/2 +1)..m 遍历您的列表（反向）（假设 m 是偶数）删除节点并将其插入第 i+1 个位置

或从 i in (m/2 +1)..m 遍历您的列表（假设 m 是偶数）删除节点并将其插入第 m-i+1 个位置

Answer 2

你可以使用这个算法：o(n) 时间复杂度

计算列表中的节点数(n)。
将最后 n/2 个节点放入堆栈中。
从头开始遍历列表。
对每一个遍历的元素，从栈中弹出该元素，使其成为遍历元素的下一个元素。
这样做直到堆栈变空。
切记将最后一个节点的next指针改为NULL。

(如果是奇数即使栈为空也得再遍历一个元素)

更改单链表中节点的顺序

Change the order of nodes in a single-linked list

c

algorithm

linked-list

data-structures