mzoe666888

V1

2022/04/16阅读:18主题:兰青

内卷大厂系列《链表反转三连击》

大厂高频算法面试题:《链表反转系列》,面试官想考察的目的:手稳不稳,coding能力,指针指向问题,链表反转几乎是高频中高频,您将学到通过有限变量即可实现链表反转,快来一起学习吧!

一、反转单向链表

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例 1

输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

示例 2

输入:head = [1,2]
输出:[2,1]

示例 3

输入:head = []
输出:[]

leetcode

1、分析

给定一个单链表的头head,完成链表的逆序调整。

方法一:有限变量搞定,定义两个变量,pre指针,next指针,pre指针指向当前节点的上一个节点,next指针指向当前节点的下一个节点。最优解,时间复杂度O(N),额外空间复杂度O(1)

方法二:递归

2、实现

1、方法一

public static class ListNode {
    int val;
    ListNode next;
}

public static ListNode reverseList(ListNode head) {
    ListNode pre = null;
    ListNode next = null;
    while (head != null) {
        next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    return pre;
}

2、方法二

public static class ListNode {
    int val;
    ListNode next;
}   

public static ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode newList = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newList;
}

二、反转双向链表

给定一个双链表的头head,完成链表的逆序调整

1、分析

提前记录下一个节点next,当前节点的next指向pre,当前节点的last指向next,pre的next指向当前节点,当前节点跳下一个

2、实现

// 双链表定义
public static class DoubleNode {
    public int value;
    public DoubleNode last;
    public DoubleNode next;

    public DoubleNode(int data) {
        value = data;
    }
}

// 双链表反转(两个指针搞定)
public static DoubleNode reverseDoubleList(DoubleNode head) {
    DoubleNode pre = null;
    DoubleNode next = null;
    while (head != null) {
        next = head.next;
        head.next = pre;
        head.last = next;
        pre = head;
        head = next;
    }
    return pre;
}

三、反转部分单向链表

给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。

示例 1

输入:head = [1,2,3,4,5], left = 2, right = 4
输出:[1,4,3,2,5]

示例 2

输入:head = [5], left = 1, right = 1
输出:[5]

进阶: 你可以使用一趟扫描完成反转吗?

leetcode

1、分析

可能存在换头的情况,所以函数应该返回调整后的新节点。

方法一:遍历一遍链表,先找到left和right节点,即反转链表的开始部分和结束部分。

  1. 先判断是否满足 1≤left≤right≤N,如果不满足,则直接返回原来的头节点。
  2. 找到第left-1个节点fPre和第right+1个节点tPos,fPre就是要反转部分的前一个节点,tPos是反转部分的后一个节点。把反转部分先反转,然后正确的连接fPre和tPos
  3. 如果fPre为null,说明反转部分是包含头节点的,则返回新的头节点,如果fPre不为null,则返回旧的头节点。

方法二:利用头插法进行反转链表,待反转的节点每次都往头部插入。

2、实现

1、方法一

public static class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

// 找到反转链表的开始节点和结束节点,正常反转
public ListNode reverseBetween(ListNode head, int from, int to) {
    int len = 0;
    ListNode node1 = head;
    ListNode fPre = null// from节点的前一个节点
    ListNode tPos = null// to节点的下一个节点
    while (node1 != null) { // 找到反转链表开始节点的前一个节点和结束节点的下一个节点
        len++;
        fPre = len == from - 1 ? node1 : fPre;
        tPos = len == to + 1 ? node1 : tPos;
        node1 = node1.next;
    }
    if (from > to || from < 1 || to > len) {
        return head;
    }
    node1 = fPre == null ? head : fPre.next;
    ListNode node2 = node1.next;
    node1.next = tPos;
    ListNode next = null;
    while (node2 != tPos) { // 反转from到to上的节点
        next = node2.next;
        node2.next = node1;
        node1 = node2;
        node2 = next;
    }
    if (fPre != null) {
        fPre.next = node1;
        return head;
    }
    return node1;
}

2、方法二

public static class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

public static ListNode reverseBetween(ListNode head, int left, int right) {
    if (head == null || left == right) {
        return head;
    }
    ListNode newHead = new ListNode(0);
    newHead.next = head;
    ListNode pre = newHead;
    for (int i = 0; i < left - 1; i++) {
        pre = pre.next;
    }
    ListNode cur = pre.next;
    ListNode next = null;
    for (int i = 0; i < right - left; i++) {
        next = cur.next;
        cur.next = next.next;
        next.next = pre.next;
        pre.next = next;
    }
    return newHead.next;
}

四、总结

链表相关的问题几乎都是coding问题,手稳不稳!指针指向问题!

单链表:值,一条next指针

双链表:值,一条pre指针,一条next指针

玩出无尽的花样!

分类:

后端

标签:

数据结构与算法

作者介绍

mzoe666888
V1