LeetCode 707. 设计链表

Categories:

题目描述
思路分析
1. 解法一：哨兵节点 + 单链表（推荐）
相似题目

题目描述

✅ 707. 设计链表

思路分析

解法一：哨兵节点 + 单链表（推荐）

核心思路：

维护一个哨兵头结点和链表长度 size。

get、addAtIndex、deleteAtIndex 均先定位到前驱节点再操作。

统一边界判断，保证 O(1) 插入删除、O(n) 访问。

复杂度分析：

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

空间复杂度：O(1) 额外空间。

class MyLinkedList {
    private final ListNode dummy;
    private int size;

    public MyLinkedList() {
        dummy = new ListNode(0);
        size = 0;
    }

    public int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }

        ListNode cur = dummy.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }

        return cur.val;
    }

    public void addAtHead(int val) {
        addAtIndex(0, val);
    }

    public void addAtTail(int val) {
        addAtIndex(size, val);
    }

    public void addAtIndex(int index, int val) {
        if (index > size) {
            return;
        }

        if (index < 0) {
            index = 0;
        }

        ListNode prev = dummy;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }

        ListNode node = new ListNode(val);
        node.next = prev.next;
        prev.next = node;
        size++;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }

        ListNode prev = dummy;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }

        prev.next = prev.next.next;
        size--;
    }

    private static class ListNode {
        int val;
        ListNode next;

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

type MyLinkedList struct {
	dummy *ListNode
	size  int
}

type ListNode struct {
	Val  int
	Next *ListNode
}

func Constructor() MyLinkedList {
	return MyLinkedList{dummy: &ListNode{Val: 0}, size: 0}
}

func (l *MyLinkedList) Get(index int) int {
	if index < 0 || index >= l.size {
		return -1
	}

	cur := l.dummy.Next
	for i := 0; i < index; i++ {
		cur = cur.Next
	}

	return cur.Val
}

func (l *MyLinkedList) AddAtHead(val int) {
	l.AddAtIndex(0, val)
}

func (l *MyLinkedList) AddAtTail(val int) {
	l.AddAtIndex(l.size, val)
}

func (l *MyLinkedList) AddAtIndex(index int, val int) {
	if index > l.size {
		return
	}

	if index < 0 {
		index = 0
	}

	prev := l.dummy
	for i := 0; i < index; i++ {
		prev = prev.Next
	}

	node := &ListNode{Val: val, Next: prev.Next}
	prev.Next = node
	l.size++
}

func (l *MyLinkedList) DeleteAtIndex(index int) {
	if index < 0 || index >= l.size {
		return
	}

	prev := l.dummy
	for i := 0; i < index; i++ {
		prev = prev.Next
	}

	prev.Next = prev.Next.Next
	l.size--
}

相似题目

题目	难度	考察点
206. 反转链表	简单	链表
203. 移除链表元素	简单	链表
86. 分隔链表	中等	链表
147. 对链表进行插入排序	中等	链表
92. 反转链表 II	中等	链表

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/70476717