本题题解，可以参考代码随想录链表设计题
#include<iostream>
using namespace std;
// 定义链表节点结构体
struct LinkedNode {
int val;
LinkedNode* next;
LinkedNode(int val):val(val), next(nullptr){}
};
int _size = 0;
LinkedNode* _dummyHead = new LinkedNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点
// 获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点
int get(int index) {
if (index > (_size - 1) || index < 0) {
return -1;
}
LinkedNode* cur = _dummyHead->next;
while(index--){ // 如果--index 就会陷入死循环
cur = cur->next;
}
return cur->val;
}
// 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点
void addAtHead(int val) {
LinkedNode* newNode = new LinkedNode(val);
newNode->next = _dummyHead->next;
_dummyHead->next = newNode;
_size++;
}
// 在链表最后面添加一个节点
void addAtTail(int val) {
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* cur = _dummyHead;
while(cur->next != nullptr){
cur = cur->next;
}
cur->next = newNode;
_size++;
}
// 在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
// 如果index 等于链表的长度，则说明是新插入的节点为链表的尾结点
// 如果index大于链表的长度，则返回空
// 如果index小于0，则在头部插入节点
int addAtIndex(int index, int val) {
if(index > _size) return -1;
if(index < 0) return -1;
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* cur = _dummyHead;
while(index--) {
cur = cur->next;
}
newNode->next = cur->next;
cur->next = newNode;
_size++;
return 0;
}
// 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的
int deleteAtIndex(int index) {
if (index >= _size || index < 0) {
return -1;
}
LinkedNode* cur = _dummyHead;
while(index--) {
cur = cur ->next;
}
LinkedNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
//delete命令指示释放了tmp指针原本所指的那部分内存，
//被delete后的指针tmp的值（地址）并非就是NULL，而是随机值。也就是被delete后，
//如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针
//如果之后的程序不小心使用了tmp，会指向难以预想的内存空间
tmp=nullptr;
_size--;
return 0;
}
// 打印链表
int printLinkedList() {
LinkedNode* cur = _dummyHead;
if (cur->next == nullptr) return -1;
while (cur->next != nullptr) {
cout << cur->next->val << " ";
cur = cur->next;
}
cout << endl;
return 0;
}
int main() {
int n, a, m, t, z;
string s;
cin >> n;
LinkedNode* head = nullptr;
while (n--) {
cin >> a;
addAtHead(a);
}
cin >> m;
while (m--) {
cin >> s;
if (s == "show") {
if (printLinkedList() == -1) cout << "Link list is empty" << endl;
}
if (s == "delete") {
cin >> t;
// 本题的删除索引是从1开始，函数实现是从0开始，所以这里是 t - 1
if (deleteAtIndex(t - 1) == -1) cout << "delete fail" << endl;
else cout << "delete OK" << endl;
}
if (s == "insert") {
cin >> t >> z;
if (addAtIndex(t - 1, z) == -1) cout << "insert fail" << endl;
else cout << "insert OK" << endl;
}
if (s == "get") {
cin >> t;
int getValue = get(t - 1);
if (getValue == -1) cout << "get fail" << endl;
else cout << getValue << endl;
}
}
}
import java.util.Scanner;
public class Main {
/* 链表节点 */
static class Node {
int val;
Node next;
public Node(int val) {
this.val = val;
}
}
/* 链表 */
static class LinkedList {
private Node head;
private int size;
public LinkedList() {
this.head = null;
this.size = 0;
}
/* 头插法 */
public void addFirst(int val) {
Node node = new Node(val);
node.next = head;
head = node;
size++;
}
/* 获取链表元素 */
public int get(int idx) {
int cnt = 0;
Node curr = head;
while (curr != null) {
if (cnt == idx) {
return curr.val;
}
cnt++;
curr = curr.next;
}
return -1;
}
/* 删除链表节点 */
public boolean delete(int idx) {
if (head == null || idx < 0 || idx >= size)
return false;
if (idx == 0) {
head = head.next;
} else {
int cnt = 0;
Node curr = head;
while (cnt < idx - 1) {
curr = curr.next;
cnt++;
}
curr.next = curr.next.next;
}
size--;
return true;
}
/* 插入元素 */
public boolean insert(int idx, int val) {
if (idx < 0 || idx > size)
return false;
if (idx == 0) {
addFirst(val);
return true;
}
int cnt = 0;
Node curr = head;
while (curr != null && cnt < idx - 1) {
curr = curr.next;
cnt++;
}
if (curr == null)
return false;
Node node = new Node(val);
node.next = curr.next;
curr.next = node;
size++;
return true;
}
/* 输出链表 */
public void show() {
if (head == null) {
System.out.println("Link list is empty");
return;
}
Node curr = head;
while (curr != null) {
System.out.print(curr.val + " ");
curr = curr.next;
}
System.out.println();
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
LinkedList linkedList = new LinkedList();
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
int num = sc.nextInt();
linkedList.addFirst(num);
}
int m = sc.nextInt();
for (int i = 0; i < m; i++) {
String operation = sc.next();
if ("get".equals(operation)) {
int a = sc.nextInt();
int result = linkedList.get(a - 1);
if (result != -1) {
System.out.println(result);
} else {
System.out.println("get fail");
}
} else if ("delete".equals(operation)) {
int a = sc.nextInt();
boolean deleteResult = linkedList.delete(a - 1);
if (deleteResult) {
System.out.println("delete OK");
} else {
System.out.println("delete fail");
}
} else if ("insert".equals(operation)) {
int a = sc.nextInt();
int e = sc.nextInt();
boolean insertResult = linkedList.insert(a - 1, e);
if (insertResult) {
System.out.println("insert OK");
} else {
System.out.println("insert fail");
}
} else if ("show".equals(operation)) {
linkedList.show();
}
}
sc.close();
}
}#定义链表节点
class LinkedNode:
def __init__(self, val = 0, next = None):
self.val = val
self.next = next
#定义链表基本操作
class MyLinkedList:
def __init__(self):
self._size = 0
self._dummyHead = LinkedNode(0)
#获取到第index个节点数值，如果index是非法数值直接返回-1， 注意index是从0开始的，第0个节点就是头结点
def get(self, index):
if index > (self._size - 1) or index < 0:
return -1
cur = self._dummyHead.next
while index:
cur = cur.next
index -= 1
return cur.val
#在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点
def addAtHead(self, val):
newNode = LinkedNode(val)
newNode.next = self._dummyHead.next
self._dummyHead.next = newNode
self._size += 1
#在链表最后面添加一个节点
def addAtTail(self, val):
newNode = LinkedNode(val)
cur = self._dummyHead
while cur.next:
cur = cur.next
cur.next = newNode
self._size += 1
#在第index个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
def addAtIndex(self, index, val):
if index > self._size:
return -1
if index < 0:
return -1
newNode = LinkedNode(val)
cur = self._dummyHead
while index:
cur = cur.next
index -= 1
newNode.next = cur.next
cur.next = newNode
self._size += 1
return 0
#删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的
def deleteAtIndex(self, index):
if index >= self._size or index < 0:
return -1
cur = self._dummyHead
while index:
cur = cur.next
index -= 1
tmp = cur.next
cur.next = cur.next.next
del tmp
self._size -= 1
return 0
#打印链表
def printLinkedList(self):
cur = self._dummyHead
if cur.next == None:
return -1
while cur.next:
print(cur.next.val, end = ' ')
cur = cur.next
print()
return 0
if __name__ == "__main__":
while True:
mylinklist = MyLinkedList()
try:
# 读取链表长度和链表数值
n, *nums = list(map(int, input().split()))
# 初始化链表
for i in range(n):
mylinklist.addAtHead(nums[i])
# 读取操作的个数
m = int(input())
for i in range(m):
s = input().split()
if s[0] == "show":
if mylinklist.printLinkedList() == -1:
print("Link list is empty")
if s[0] == "delete":
t = int(s[1])
if mylinklist.deleteAtIndex(t - 1) == -1:
print("delete fail")
else:
print("delete OK")
if s[0] == "insert":
t = int(s[1])
z = int(s[2])
if mylinklist.addAtIndex(t - 1, z) == -1:
print("insert fail")
else:
print("insert OK")
if s[0] == "get":
t = int(s[1])
getValue = mylinklist.get(t - 1)
if getValue == -1:
print("get fail")
else:
print(getValue)
except:
breakpackage main
import (
"errors"
"fmt"
)
// 由于 leetcode 中的链表操作下标都是基于0开始，本题从1开始，故每个函数里面对传入的index做减一操作
func main() {
var n int
_, err := fmt.Scan(&n)
if err != nil {
return
}
list := Constructor()
for i := 0; i < n; i++ {
var data int
_, err = fmt.Scan(&data)
if err != nil {
return
}
list.insert(1, data)
}
var m int
_, err = fmt.Scan(&m)
if err != nil {
return
}
for i := 0; i < m; i++ {
var s string
_, err = fmt.Scan(&s)
if err != nil {
return
}
switch s {
case "get":
var index int
_, err = fmt.Scan(&index)
if err != nil {
return
}
val, err := list.get(index)
if err != nil {
fmt.Println(err.Error())
} else {
fmt.Println(val)
}
case "delete":
var index int
_, err = fmt.Scan(&index)
if err != nil {
return
}
err := list.delete(index)
if err != nil {
fmt.Println(err.Error())
} else {
fmt.Println("delete OK")
}
case "insert":
var index, val int
_, err = fmt.Scan(&index, &val)
if err != nil {
return
}
if err = list.insert(index, val); err != nil {
fmt.Println(err.Error())
} else {
fmt.Println("insert OK")
}
case "show":
list.Show()
}
}
}
type Node struct {
val int
next *Node
}
type MyLinkedList struct {
size int
head *Node
}
func Constructor() MyLinkedList {
return MyLinkedList{}
}
// 1 2 3
func (this *MyLinkedList) get(index int) (int, error) {
index--
if this.size == 0 || index < 0 || index > this.size {
return -1, errors.New("get fail")
}
cur := this.head
for i := 0; i < index; i++ {
cur = cur.next
}
return cur.val, nil
}
func (this *MyLinkedList) insert(index, val int) error {
index--
if index < 0 || index > this.size {
return errors.New("insert fail")
}
dummyHead := &Node{next: this.head}
cur := dummyHead
for i := 0; i < index; i++ {
cur = cur.next
}
newNode := &Node{
val: val,
next: cur.next,
}
cur.next = newNode
this.size++
this.head = dummyHead.next
return nil
}
func (this *MyLinkedList) delete(index int) error {
index--
if this.size == 0 || index < 0 || index > this.size-1 {
return errors.New("delete fail")
}
dummyHead := &Node{next: this.head}
cur := dummyHead
for i := 0; i < index; i++ {
cur = cur.next
}
cur.next = cur.next.next
this.size--
this.head = dummyHead.next
return nil
}
func (this *MyLinkedList) Show() {
if this.size == 0 {
fmt.Println("Link list is empty")
return
}
cur := this.head
for cur.next != nil {
fmt.Printf("%d ", cur.val)
cur = cur.next
}
fmt.Println(cur.val)
}