LeetCode 补充题 18. 反转双向链表

Categories:

题目描述
思路分析
1. 解法一：迭代翻转指针（推荐）
相似题目

题目描述

✅ 补充题 18. 反转双向链表

思路分析

解法一：迭代翻转指针（推荐）

核心思路：

遍历双向链表，交换每个节点的 prev 与 next 指针。

迭代结束时，最后处理的节点即为新的头节点。

注意断开新头节点的 prev 指针。

复杂度分析：

时间复杂度：O(n)，其中 n 表示链表长度。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    static class Node {
        int val;
        Node prev;
        Node next;

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

    public Node reverse(Node head) {
        Node curr = head;
        Node newHead = null;

        while (curr != null) {
            Node next = curr.next;

            curr.next = curr.prev;
            curr.prev = next;

            newHead = curr;
            curr = next;
        }

        if (newHead != null) {
            newHead.prev = null;
        }

        return newHead;
    }
}

type Node struct {
	Val  int
	Prev *Node
	Next *Node
}

func reverse(head *Node) *Node {
	curr := head
	var newHead *Node

	for curr != nil {
		next := curr.Next

		curr.Next = curr.Prev
		curr.Prev = next

		newHead = curr
		curr = next
	}

	if newHead != nil {
		newHead.Prev = nil
	}

	return newHead
}

相似题目

题目	难度	考察点
206. 反转链表	简单	迭代翻转
92. 反转链表 II	中等	链表
24. 两两交换链表中的节点	中等	链表
25. K 个一组翻转链表	困难	链表
147. 对链表进行插入排序	中等	链表

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/16588586