侧边栏壁纸
博主头像
LYMTICS

海纳百川,有容乃大

  • 累计撰写 45 篇文章
  • 累计创建 37 个标签
  • 累计收到 19 条评论

目 录CONTENT

文章目录

链表学习总结

LYMTICS
2022-01-22 / 0 评论 / 0 点赞 / 99 阅读 / 1,844 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-01-22,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

链表学习总结

参考文章:

总结

(转自参考文章)

  • 一个原则:多画图
  • 两个考点:指针的修改链表的拼接
  • 三个注意:
    1. (由于操作顺序等问题,或者特殊情况没考虑到,导致出现环)
    2. 边界
    3. 前后序 (这个我倒是不太理解)
  • 技巧:
    1. 虚拟头:如果头节点可能发生修改
    2. 快慢指针:适用于部分题型

常用操作

反转链表

这个问题的关键就是now.next = before (反转操作时),now.next 会丢失,所以需要一个额外的变量保存这个值。

方法一:

(图源LeetCode优质题解,下同)

// 双指针法
public ListNode reverseList(ListNode head) {
    ListNode tail = null;
    ListNode tmp = null;
    while(head != null) {
        tmp = head.next;
        head.next = tail;
        tail = head;
        head = tmp;
    }
    return tail;
}

方法二:

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) {return null;}
        ListNode cur = head;
        ListNode tmp = null;
        // 注意这里有可能head是null,所以要在前面做一个判断
        while(head.next != null) {
            tmp = head.next.next;

            head.next.next = cur;
            cur = head.next;
            
            head.next = tmp;
        }

        return cur;
    }
}

方法三:递归:

这个要递归调用,内存开销会大一点吧(那还不如借助栈?)

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode tmp = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return tmp;
    }
}

递归

  1. 找终止条件:本题终止条件很明显,当递归到链表为空或者链表只剩一个元素的时候,没得交换了,自然就终止了。
  2. 找返回值:返回给上一层递归的值应该是已经交换完成后的子链表。
  3. 单次的过程:因为递归是重复做一样的事情,所以从宏观上考虑,只用考虑某一步是怎么完成的。我们假设待交换的俩节点分别为head和next,next的应该接受上一级返回的子链表(参考第2步)。就相当于是一个含三个节点的链表交换前两个节点,就很简单了,想不明白的画画图就ok。

(源题目评论)

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode next = head.next;
        head.next = swapPairs(next.next);
        next.next = head;
        return next;
    }
}

这个题结合了206. 翻转链表24. 两两交换链表中的节点,由于对每一段的处理有重复的部分,所以考虑用递归。

递归三要素:

  1. 返回值: 返回的是这一段反转后的头节点
  2. 终止条件: 当剩余数量不够k时,终止循环,返回头节点
  3. 处理: 对长度为k的链表进行反转(思路痛206题)
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 特殊情况处理
        if (k == 1) return head;
        // 终止条件
        ListNode tmp = head;
        int kk = k;
        while (k-- > 1 && tmp != null) {
            tmp = tmp.next;
        }
        if (tmp == null) {
            return head;
        }
        // 每一轮的翻转操作
        ListNode pre = head.next;
        tmp = head;
        k = kk;
        while (k-- > 1) {
            ListNode tmp2 = pre.next;
            pre.next = tmp;;
            tmp = pre;
            pre = tmp2;
        }
        head.next = reverseKGroup(pre, kk);

        // 返回值
        return tmp;
    }
}
0

评论区