美文网首页
反转链表及其考察的知识点

反转链表及其考察的知识点

作者: 泰克尼客 | 来源:发表于2021-04-22 10:52 被阅读0次

什么是反转链表

如下图所示,原来的链表指向性是从第一个节点1依次指向最后一个节点5,反转链表后,要让原来的链表中的最后一个节点变成第一个节点,并逆转整个链表的指向性。

反转链表

考察的知识点

链表相关的操作,难度都不大,但很能够考察思维的严密性,主要体现在:

  1. 处理每个节点时,各个操作的先后顺序;
  2. 边界情况的考虑,例如,对于头节点和尾节点的考虑是否完善。

如果能充分考虑以上两点,那么链表相关的操作就大体没有问题了。

思路

当我们遍历到某一个节点cur时,面临的情况如下:

cur节点
根据题意,我们的目标是:
  1. cur节点指向prev节点
  2. next节点成为新的cur节点,从而驱动下一轮遍历

所以,整个遍历过程要有两个指针,cur节点用来指向当前节点,prev节点用来指向上一个节点。并且,由于既要使得cur节点指向prev,又要让它过渡到next节点,所以在处理每个cur节点时,必然要用一个临时指针来协助完成这件事,伪码如下:

# 获取next节点
tmp = cur->next;
# 使得cur指向其prev
cur -> next = prev;
# 更新prev指针,以供下一轮遍历使用
prev = cur;
# 更新cur指针,开启下一轮遍历
cur = tmp;

指针移动后,新的节点状态如下图所示:


指针更新后的节点状态

代码实现

下面附上C代码的实现,请注意双节点prevcur的初始化和更新的过程。

struct ListNode* reverseList(struct ListNode *head){
    // 初始化双节点prev和cur
    struct ListNode *prev = NULL;
    struct ListNode *cur = head;

    while(cur) {
        struct ListNode* tmp = cur->next;
        // 反转
        cur->next = prev;

        // 更新prev和cur节点
        prev=cur;
        cur=tmp;
    }
}

相关文章

  • 反转链表及其考察的知识点

    什么是反转链表 如下图所示,原来的链表指向性是从第一个节点1依次指向最后一个节点5,反转链表后,要让原来的链表中的...

  • 234. Palindrome Linked List

    知识点: 快慢指针 链表反转链表反转的四行代码必须熟记

  • 单链表的就地逆置--java实现(含头节点和不包含头节点)

    前沿:链表是面试中经常问道的知识点,比如链表反转,就地反转,判断单链表是否相交,判断链表是否有环等都是常问的问题....

  • 链表类算法题汇总

    算法题目中常考察的链表操作无非以下几种: 链表反转 链表合并 寻找链表中点 寻找链表倒数第 K 个节点 删除链表节...

  • 【链表】--k个一组反转(hard)

    思路:考察链表反转 链表反转 你的算法只能使用常数的额外空间。你不能只是单纯的改变节点内部的值,而是需要实际进行节...

  • [Leetcode] [Tag 链表] Python 刷题总结

    链表的结构 链表的题不难,多在于考察对链表操作的熟练度,问题常常在于链表是单向的,需要对链表的删除、反转、获取第n...

  • Algorithm小白入门 -- 单链表

    单链表递归反转链表k个一组反转链表回文链表 1. 递归反转链表 单链表节点的结构如下: 1.1 递归反转整个单链表...

  • 单链表 常用操作(golang)

    (单链表备忘记录)知识点: 单链表结构 创建链表方法头插法创建尾插法创建 遍历链表 逆序反转链表迭代递归头插法就地...

  • 链表反转

    循环反转链表 递归反转链表

  • 5个链表的常见操作

    链表 链表反转 LeetCode206:给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。 环路检...

网友评论

      本文标题:反转链表及其考察的知识点

      本文链接:https://www.haomeiwen.com/subject/gxjxrltx.html