链表反转类算法题

反转链表类

NO1. 反转链表

给定一个长度为 n 的链表,反转该链表,输出表头。

链表反转类算法题插图

方法一:迭代法(推荐使用)

算法流程:

  • step 1 :特殊情况判断,空链表或只有一个结点的链表,直接返回头结点;
  • step 2 :设置两个指针curprevcur指向当前结点,prev指向上一个结点(初始为 null);
  • step 3 :遍历整个链表,每到一个结点,断开当前结点cur与下一个结点 cur.next 的指针,并用临时变量 temp 记录下一个结点,然后当前结点的next指向上一个结点(实现反转);
    • 轮换cur与上一个结点prev,进行下一个结点反转;
    • 循环退出条件为 cur == null
  • step 4 :返回 prev(反转后,原尾节点变成头结点);

链表反转类算法题插图1

代码实现:

public class Main {
    public ListNode ReverseList(ListNode head) {
        // 特殊情况判断
		if(head == null || head.next == null) 	return head;
        // 双指针
        ListNode prev = null, cur = head;
        while(cur != null) {
            ListNode temp = cur.next;	// 断开链表,要记录后续⼀个
            cur.next = prev;	// 当前的next指针指向前⼀个
            prev = cur;		// 前⼀个更新为当前
            cur = temp;		// 当前更新为刚刚记录的后⼀个
        }
    }
}

复杂度分析:

  • 时间复杂度:(O(N)),遍历链表一次;
  • 空间复杂度:(O(1)),申请常数个变量;

方法二:递归

根据迭代法,每当我们反转链表中某个结点以后,要遍历进入下一个结点进行反转,相当于对后面的子链表进行反转,那这就是一个子问题,因此我们可以使用递归来解决。

  • 终止条件:当到达链表尾部,要么当前指针为空,要么下一个指针为空,直接向上层返回当前结点;
  • 返回值:每一层向上一层返回翻转后子问题的头结点;
  • 本层任务:先进入后一个结点作为子问题,继续反转,然后记录返回的头结点,连接在本层结点的后面;

算法流程:

  • step 1 :递归向下遍历链表,直到遍历到最后一个结点;
  • step 2 :往上一次逆转两个结点;
  • step 3 :逆转后的尾连接本层的结点 head,并断开两节点的原指针(置为 null);

链表反转类算法题插图2

public class Main {
    public ListNode ReverseList(ListNode head) {
        // 递归停止条件
		if(head == null || head.next == null) 	return head;
        ListNode newHead = ReverseList(head.next);	// 反转下一个
        // 本层任务,如
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

复杂度分析:

  • 时间复杂度:(O(N)),遍历链表一次;
  • 空间复杂度:(O(N)),递归栈的深度就是链表的长度(N)

NO2. 链表内指定区间反转

将一个结点为 size 的链表 m 位置到 n 位置之间的区间反转;

链表其他部分不变,返回头结点;

方法一:头插法迭代(推荐)

第一步肯定是要先找到第 m 个位置,然后不断反转,直到到达 n 位置;由于m可能为1,即头结点,那反转之后 head 就不再指向头结点了,所以,先构造一个虚拟头结点;

算法流程:

  • step 1 :可以在链表头添加一个虚拟头结点,后续返回时去掉就好了;
  • step 2 :使用两个指针,cur指向当前结点,prev指向前驱节点;
  • step 3 :依次遍历链表,到达第 m 个位置;
  • step 4 :从 m 到 n 位置的结点,依次断掉指向下一个结点的指针,指向前驱,实现反转;
  • step 5 :返回虚拟头结点的next

链表反转类算法题插图3

代码实现:

public class Solution {
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // 虚拟头结点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // 双指针(反转链表常规操作)
        ListNode prev = dummy, cur = head;
        // 找到第 m 个结点
        for(int i = 1; i 

复杂度分析:

  • 时间复杂度:(O(N)),最坏情况下,需要遍历链表一次;
  • 空间复杂度:(O(1)),申请常数个变量;

方法二:递归

链表反转类算法题插图4

算法流程:

  • step 1 :先利用递归找到反转区间的起点;
  • step 2 :再利用递归从第 n 个位置开始反转,往上拼接;

代码实现:

public class Solution {    
	public ListNode reverseBetween (ListNode head, int m, int n) {
        // 找到第 m 个结点,执行反转
        if(m == 1)    return reverse(head, n);
        // 找 第 m 个结点
        ListNode node = reverseBetween(head.next, m - 1, n - 1);
        head.next = node;	// 拼接已翻转
        return head;
    }
    
    ListNode tmp = null;    // tmp用来暂存第n个结点的后继
    public ListNode reverse(ListNode head, int n){
        // 递归停止
        if(n == 1) {
            tmp = head.next;
            return head;
        }
        ListNode node = reverse(head.next, n - 1);    //进⼊⼦问题
        head.next.next = head; //反转
        head.next = tmp; //拼接
        return node;	// 返回上一层
    }
}

复杂度分析:

  • 时间复杂度:(O(N)),最坏情况下,需要遍历链表一次;
  • 空间复杂度:(O(N)),最坏情况下,递归栈的深度就是链表的长度(N)

NO.3 链表结点每K个一组翻转

给定一个链表,从头开始每 K 个作为一组,将每组的链表结点翻转;

组与组之间的位置关系保持不变;

如果最后链表末尾剩余不足 K 个结点,则不反转,直接放在尾部;

方法一:头插法迭代

链表反转类算法题插图5

算法流程:

  • step 1 :反转过程中要改变 head 指针,就得设个虚拟头结点,定义双指针 precur
  • step 2 :统计链表总长度 len ,用于得出翻转组数 len / k
  • step 3 :外循环控制翻转组数,内循环控制组内的k个结点翻转(头插 k - 1次)

代码实现:

public class Main {
    public ListNode reverseKGroup (ListNode head, int k) {
        // 特判
        if(head == null || head.next == null || k 

复杂度分析:

  • 时间复杂度:(O(N)),需要遍历链表两次;
  • 空间复杂度:(O(1)),申请常数个变量;

方法二:递归

终止条件:当进行到最后一个分组,元素个数不足 k 个,就将剩余的最后一个分组直接返回给上层;

返回值:每一层要返回给上层的是翻转后这个分组的头结点,并且后面已经连接好了所有的已翻转好的分组链表;

本层任务:先遍历 k 次,找到该分组尾结点的位置,然后从分组的头结点遍历到尾结点,依次翻转;

算法流程:

  • step 1 :翻转前,找到每次分组的尾节点的下一个结点,即下一分组的头结点
  • step 2 :采用常规的翻转链表操作;
  • step 3 :递归进行拼接;

链表反转类算法题插图6

代码实现:

public class Main{
    public ListNode reverseKGroup (ListNode head, int k) {
        
        ListNode tail = head;
        // tail指向本组尾节点的下一个节点,即下一分组的头结点
        for(int i = 0; i 

复杂度分析:

  • 时间复杂度:(O(N)),一共遍历链表 n 个结点;
  • 空间复杂度:(O(1)),申请常数个变量;

总结

链表反转类算法题,有两种解决思路:

  1. 遍历链表,利用两个滚动指针,不断改变当前结点的 next 指针的指向(当前结点的 next 指向前驱),每次改变指针时都要暂存下一个节点;
  2. 头插法,每次把结点头插到 prev 指针后,实现反转;

文章来源于互联网:链表反转类算法题

THE END
分享
二维码