首页 > 教程

c++之按序列反转链表

slbcun
2025-04-08
1484 ℃

int main() {

ListNode *p0 = new ListNode(0);
ListNode *p1 = new ListNode(1);
ListNode *p2 = new ListNode(2);
ListNode *p3 = new ListNode(3);
ListNode *p4 = new ListNode(4);
ListNode *p5 = new ListNode(5);
ListNode *p6 = new ListNode(6);

p1->next = p2;
p2->next = p3;
p3->next = p4;
p4->next = p5;
p5->next = p6;

ListNode *head = Newnode(p1, 2, 5);

while (head) {
cout<<head->val;
head = head->next;
}

return 0;
}

这是一个链表的结构，那么根据我们这个主函数里面的显示的，也就说在这个函数里面啊，是newnoe。然后把这个函数传进。首先我们把列表传进去，然后根据特定的序列。来进行反转，比如我这里是P12到五，那么原本它应该是一个123456。然后经过我的反转之后，2~5进行了反转，也就是2.5就反了。然后1和6不变。来输出这个序列。

答案是154326

ListNode* revelnode(ListNode *head) {
if (head == NULL) return NULL;
ListNode *p = head->next;
ListNode *q = head;
q->next = nullptr;

while (p) {
head = p;
p = p->next;
head->next = q;
q = head;
}

return head;
}

那么如果要实现这个按位移按序列反转，首先就应该实现全反转，也就是说一个123456。输入进去，那么我们得到的结果应该是一个倒叙的654321。好的，第一步，把这个head传进去，那么这里的head它实际上就是反转之后的最后节点啊，首先两个指针P和Q，P的话是指向hi的下一个节点，Q是hi的节点，那这里的Q。

Q的下一个节点为空，也就是说这里是断开了。那么，本来它这个Q的下一个节点它是有节点的啊，然后这一步就把它的这个下一步的节点断开了啊，以便我们用来力学。然后，金着是关键的地方。然后，就是一个微的循环啊。首先，检查我们这个P节点，那么，我们的P节点如果只要它不为空的情况下，我们就会执行。当它为空的时候，代表我们的整个反转其实上已经完成了。然后hi=P，P=P的下一个节点啊，也就是说我们的head是现在的PP的话，然后移动到下一个节点。然后，Hi的下一个点等于Q啊，完成这个时，也就是刚才断开的时候，我们把这个断开的节点连接到现在的hi，就完成列句了。然后不断的重复这个过程。

最后把序列段全转后，与前后进行拼接操作

code： https://pan.quark.cn/s/3fb04303e5b3