当前位置:网站首页><代码随想录二刷>链表

<代码随想录二刷>链表

2022-07-07 15:41:00 51CTO


文章目录


203. 移除链表元素

 ​题目描述​

给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。

示例 1:

      
      
输入:head = [ 1, 2, 6, 3, 4, 5, 6], val = 6
输出:[ 1, 2, 3, 4, 5]
  • 1.
  • 2.

示例 2:

      
      
输入:head = [], val = 1
输出:[]
  • 1.
  • 2.

示例 3:

      
      
输入:head = [ 7, 7, 7, 7], val = 7
输出:[]
  • 1.
  • 2.

思路分析

双指针

先为原始链表创建一个虚拟头结点(便于操作),然后定义两个指针,pre指向前一个节点,cur指向当前节点.

当前节点满足条件,则进行移除操作.

最后删除创建的虚拟头结点.

图解过程:

<代码随想录二刷>链表_c++

参考代码

      
      
#include<bits/stdc++.h>
using namespace std;

struct ListNode {
int val;
ListNode * next;
ListNode(): val( 0), next( nullptr) {}
ListNode( int x): val( x), next( nullptr) {}
ListNode( int x, ListNode * next): val( x), next( nullptr) {}
};

//采用双指针
ListNode * removeElements( ListNode * node, int val) {
ListNode * head = new ListNode( - 1, node) ; //定义头结点
ListNode * pre = head; //初始化
ListNode * cur = head -> next; //这里也可以直接使用一个cur变量来删除节点,我们定义两个,逻辑更加清晰
ListNode * temp;
while( cur != NULL) {
if( cur -> val == val) {
temp = cur;
pre -> next = cur -> next;
cur = cur -> next;
delete temp;
} else {
pre = cur;
cur = cur -> next;
}
}
//删除虚拟头结点
temp = head -> next;
delete head;
return temp;
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.

206. 反转链表

 ​题目描述​

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

示例 1:

<代码随想录二刷>链表_edn_02

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

示例 2:

<代码随想录二刷>链表_c++_03

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

示例 3:

      
      
输入:head = []
输出:[]
  • 1.
  • 2.

思路分析

方法一:双指针

基本思路:从前往后将指针的方向改变,返回最后一个节点
使用pre指向前一个节点,cur代表当前节点,从第一个节点开始进行遍历,每次让cur指向pre,之后cur继续遍历下一个节点,直至链表遍历完毕.

<代码随想录二刷>链表_edn_04

方法二:递归(从前往后改变指针方向)

思路和方法一基本一致,递归实际上就是自己调用自己,每次的操作一致.

  • 每次我们需要改变指针指向,需要操作两个节点,当前节点cur和上一个节点pre,所以这就是递归函数的参数.
  • 递归的结束条件就是当前节点为NULL,则不再需要改变方向了.递归结束.

方法三:递归(从后往前改变指针方向)

参考代码

方法一:双指针

      
      
//方法一:双指针法
ListNode * reverseList( ListNode * head) {
if( head == NULL || head -> next == NULL) { //判断0个和1个节点情况,不用进行反转
return head;
}
ListNode * pre = NULL, * cur = head, * temp = head -> next;
//开始 从前往后改变指针的指向
while( cur) {
temp = cur -> next; //保存下一个节点
cur -> next = pre; //改变指向
pre = cur; //pre后移动
cur = temp; //cur后移动
}
return pre;
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.

方法二:递归(从前往后改变指针方向)

      
      
//方法二:递归法1 先改变指针方向,再继续进行递归
ListNode * reverse( ListNode * pre, ListNode * cur) { //返回值主要是用来递归完成之后返回头结点的,无其他用途
if( cur == NULL) {
return pre;
}
ListNode * temp = cur -> next;
cur -> next = pre; //修改指针方向
return reverse( cur, temp) ;
}

ListNode * reverseList( ListNode * head) {
if( head == NULL || head -> next == NULL) { //判断0个和1个节点情况,不用进行反转
return head;
}
return reverse( NULL, head);
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.

方法三:递归(从后往前改变指针方向) 目前测试不通过…

      
      
//方法三:递归法2 先进行递归,后改变指针方向 ???不知道为啥错了..
ListNode * resNode = new ListNode( - 1);
ListNode * solve( ListNode * cur) {
if( cur == NULL) { //结束条件
return resNode;
}
ListNode * pre = solve( cur -> next);
pre -> next = cur;
return cur;
}
ListNode * reverseList( ListNode * head) {
if( head == NULL || head -> next == NULL) { //判断0个和1个节点情况,不用进行反转
return head;
}
solve( head);
ListNode * head = resNode -> next;
delete resNode;
return head;
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.

24. 两两交换链表中的节点

 ​题目描述​

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

示例 1:

<代码随想录二刷>链表_edn_05

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

示例 2:

      
      
输入:head = []
输出:[]
  • 1.
  • 2.

示例 3:

      
      
输入:head = [ 1]
输出:[ 1]
  • 1.
  • 2.

思路分析

题目的要求是交换相邻的节点,题目也说了是这两个节点的顺序发生改变,而不是仅仅交换下值.而且如果当前节点只有一个,则肯定不需要交换啦.

接下来我们用图解来表示:

<代码随想录二刷>链表_链表_06

<代码随想录二刷>链表_算法_07

根据图中,我们可以使用三个辅助变量便可完成操作.

参考代码

      
      
#include<bits/stdc++.h>
using namespace std;

//节点定义
struct ListNode{
int val;
ListNode * next;
ListNode(){}
ListNode( int x): val( x), next( nullptr){
}
ListNode( int x, ListNode * next): val( x), next( next){
}

};

ListNode * swapPairs( ListNode * head) {
if( head == NULL || head -> next == NULL){ //没有结点或者只有一个结点时
return head;
}
ListNode * dummyHead = new ListNode( - 1, head); //创建虚拟头结点
ListNode * cur = dummyHead, * node1, * node2, * node3; //创建当前节点cur以及辅助节点node1、node2、node3
while( cur -> next && cur -> next -> next){
node1 = cur -> next;
node2 = cur -> next -> next;
node3 = cur -> next -> next -> next;
cur -> next = node2; //执行第一步:当前0节点指向2号节点
node2 -> next = node1; //执行第二步:当前2节点指向1号节点
node1 -> next = node3; //执行第三步:当前1节点指向3号节点.
cur = node1; //更新cur
}
head = dummyHead -> next;
delete dummyHead;

return head;
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.

19. 删除链表的倒数第 N 个结点

 ​题目描述​

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

示例 1:

<代码随想录二刷>链表_c++_08

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

示例 2:

      
      
输入:head = [ 1], n = 1
输出:[]
  • 1.
  • 2.

示例 3:

      
      
输入:head = [ 1, 2], n = 1
输出:[ 1]
  • 1.
  • 2.

思路分析

方法一:逆向思维法

删除倒数第n个节点 ==> 删除正数N-n+1个节点.

图解:(以实例一为例)

<代码随想录二刷>链表_链表_09

方法一:快慢指针
先搞一个虚拟头结点,方便我们接下来的操作.

  • 第一步slow和fast都指向虚拟头结点.
  • 第二步fast向前移动n+1个节点
  • slow和fast同时向前移动,直至fast为空,则slow对应的便是目标节点的前一个节点.

图解

<代码随想录二刷>链表_edn_10

参考代码

方法一:逆向思维法

      
      
//方法一:逆向思维法 删除倒数第n个节点 ==> 删除正数N-n+1个节点.
ListNode * removeNthFromEnd( ListNode * head, int n) {
ListNode * dummyHead = new ListNode( - 1, head);
ListNode * cur, * temp;
cur = dummyHead -> next;
int N = 0, m; //总结点
while( cur) {
N ++;
cur = cur -> next;
}
//删除第n个节点
m = N - n;
cur = dummyHead;
while( m --){ //指针指向第m个位置
cur = cur -> next;
}
temp = cur -> next; //保存删除节点
cur -> next = cur -> next -> next; //进行删除
delete temp;
// delete dummyHead;
head = dummyHead -> next; //最后的head一定要重新赋值哦,因为之前的head 可能已经挂了.
delete dummyHead;
return head;
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.

方法二:双指针法

      
      
//方法二:双指针法(快慢指针法)
ListNode * removeNthFromEnd( ListNode * head, int n) {
ListNode * dummyHead = new ListNode( - 1, head);
ListNode * slow = dummyHead, * fast = dummyHead, * temp;
//fast先走n+1步
while( n >= 0) {
fast = fast -> next;
n --;
}
//slow和fast同时开始走,直到fast为NULL
while( fast != NULL) {
slow = slow -> next;
fast = fast -> next;
}
//进行删除
temp = slow -> next;
slow -> next = slow -> next -> next;
delete temp;
head = dummyHead -> next;
delete dummyHead;
return head;
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.

面试题 02.07. 链表相交

 ​题目描述​

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。

图示两个链表在节点 c1 开始相交:

<代码随想录二刷>链表_edn_11

题目数据 保证 整个链式结构中不存在环。

注意,函数返回结果后,链表必须 保持其原始结构 。

示例 1:

<代码随想录二刷>链表_c++_12

      
      
输入:intersectVal = 8, listA = [ 4, 1, 8, 4, 5], listB = [ 5, 0, 1, 8, 4, 5], skipA = 2, skipB = 3
输出:Intersected at '8'
  • 1.
  • 2.

解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。
在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。

示例 2:

<代码随想录二刷>链表_算法_13

      
      
输入:intersectVal = 2, listA = [ 0, 9, 1, 2, 4], listB = [ 3, 2, 4], skipA = 3, skipB = 1
输出:Intersected at '2'
  • 1.
  • 2.

解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。
从各自的表头开始算起,链表 A 为 [0,9,1,2,4],链表 B 为 [3,2,4]。
在 A 中,相交节点前有 3 个节点;在 B 中,相交节点前有 1 个节点。

示例 3:

<代码随想录二刷>链表_leetcode_14

      
      
输入:intersectVal = 0, listA = [ 2, 6, 4], listB = [ 1, 5], skipA = 3, skipB = 2
  • 1.

解释:从各自的表头开始算起,链表 A 为 [2,6,4],链表 B 为 [1,5]。
由于这两个链表不相交,所以 intersectVal 必须为 0,而 skipA 和 skipB 可以是任意值。
这两个链表不相交,因此返回 null 。

思路分析

题目的要求是求两个链表的交点,但是这里的交点是指针相等,不是节点里面的值相同.

看如下两个链表,目前curA指向链表A的头结点,curB指向链表B的头结点,如何求得交点呢.

<代码随想录二刷>链表_edn_15

我们可以求出两个链表的长度,并求出两个链表长度的差值,然后让curA移动到,和curB 末尾对齐的位置,如图:

<代码随想录二刷>链表_edn_16

此时我们就可以让CurA和CurB,从前往后遍历各自链表的节点,直到两者相等,此时对应的便是交点. 如果两个链表都遍历完还没有找到,则说明没有交点.

参考代码

      
      
#include<bits/stdc++.h>
using namespace std;

struct ListNode {
int val;
ListNode * next;
ListNode() {}
ListNode( int x): val( x), next( nullptr) {
}
ListNode( int x, ListNode * next): val( x), next( next) {
}
};

//方法:双指针
//先求出两条链表长度,然后最长两个指针指向最短的起始位置 ,同时向后移动.知道遇到公共结点
ListNode * getIntersectionNode( ListNode * headA, ListNode * headB) {
ListNode * pointerA = headA, * pointerB = headB;
int lenA = 0, lenB = 0, gap; //a:b代表两条链表的长度
while( pointerA) { //求LenA长度
lenA ++;
pointerA = pointerA -> next;
}
while( pointerB) { //求LenB长度
lenB ++;
pointerB = pointerB -> next;
}
始终让A的长度比B大
if( lenA > lenB) {
pointerA = headB;
pointerB = headA;
gap = lenA - lenB;
} else{
pointerA = headA;
pointerB = headB;
gap = lenB - lenA;
}
while( gap --) { //B指针移动到和A指针相同的位置
pointerB = pointerB -> next;
}
while( pointerA && pointerB) { //A和B一起向前移动
if( pointerA == pointerB){ //如果相同则直接进行返回
return pointerA;
}
pointerA = pointerA -> next;
pointerB = pointerB -> next;
}
return NULL; //如果没有公共结点,则返回NULL;
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
  • 45.
  • 46.
  • 47.
  • 48.

141. 环形链表

 ​题目描述​

给你一个链表的头节点 ​​head​​ ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 ​​next​​​ 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 ​​pos​​ 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ,则返回 ​​true​​​ 。 否则,返回 ​​false​​ 。

示例 1:

<代码随想录二刷>链表_edn_17

      
      
输入:head = [ 3, 2, 0, - 4], pos = 1
输出:true
  • 1.
  • 2.

示例 2:

<代码随想录二刷>链表_链表_18

      
      
输入:head = [ 1, 2], pos = 0
输出:true
  • 1.
  • 2.

示例 3:

<代码随想录二刷>链表_链表_19

      
      
输入:head = [ 1], pos = - 1
输出:false
  • 1.
  • 2.

思路分析

如何判断是否有环?:快慢指针

分别定义fast和slow指针,分别指向头结点,fast每次移动两个节点,slow每次移动一个节点,如果fast和slow指针在途中相遇,则说明这个链表有环.

这个过程就如同操场跑步一样,跑的快的人在一段时间后就会追上慢的人.

<代码随想录二刷>链表_c++_20

参考代码

      
      
#include<bits/stdc++.h>
using namespace std;

struct ListNode {
int val;
ListNode * next;
ListNode() {}
ListNode( int x): val( x), next( nullptr) {
}
ListNode( int x, ListNode * next): val( x), next( next) {
}
};

bool hasCycle( ListNode * head) {
ListNode * slow = head, * fast = head;
while( fast != NULL){
fast = fast -> next;
if( fast != NULL) {
fast = fast -> next;
} else{ //没有环
continue;
}
slow = slow -> next;
if( slow == fast){ //有环
return true;
}
}
return false; //没有环
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.

142. 环形链表 II

 ​题目描述​

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1:

<代码随想录二刷>链表_链表_21

      
      
输入:head = [ 3, 2, 0, - 4], pos = 1
输出:返回索引为 1
  • 1.
  • 2.

解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

<代码随想录二刷>链表_c++_22

      
      
输入:head = [ 1, 2], pos = 0
输出:返回索引为 0
  • 1.
  • 2.

解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

<代码随想录二刷>链表_算法_23

      
      
输入:head = [ 1], pos = - 1
  • 1.

解释:链表中没有环。

思路分析

本题主要考察:

  • 判断链表是否环
  • 如果有环,如何找到这个环的入口

如何判断是否有环?:快慢指针

分别定义fast和slow指针,分别指向头结点,fast每次移动两个节点,slow每次移动一个节点,如果fast和slow指针在途中相遇,则说明这个链表有环.

这个过程就如同操场跑步一样,跑的快的人在一段时间后就会追上慢的人.

<代码随想录二刷>链表_c++_24

如果有环,如何找到这个环的入口<代码随想录二刷>链表_c++_25

从头结点出发一个指针index1,从相遇节点 也出发一个指针index2,这两个指针每次只走一个节点, 那么当这两个指针相遇的时候就是 环形入口的节点。

 ​证明过程可以参考卡尔大佬的文章,讲的通俗易懂,嘿嘿嘿​

<代码随想录二刷>链表_算法_26

参考代码

      
      
#include<bits/stdc++.h>
using namespace std;

struct ListNode {
int val;
ListNode * next;
ListNode() {}
ListNode( int x): val( x), next( nullptr) {
}
ListNode( int x, ListNode * next): val( x), next( next) {
}
};

ListNode * detectCycle( ListNode * head) {
ListNode * slow = head, * fast = head, * index1, * index2;
//首先判断有环没有环
while( fast != NULL && fast -> next != NULL) {
fast = fast -> next -> next; //fast走两步
slow = slow -> next; //slow走一步
if( slow == fast) { //此时如果相遇必定是入口节点
index1 = head;
index2 = slow;
//寻找环的入口
while( index1 != index2) {
index1 = index1 -> next;
index2 = index2 -> next;
}
return index1;
}

}
return NULL; //如果无环,则会退出while循环,返回NULL
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.

707. 设计链表

 ​题目描述​

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性:val 和 next。val 是当前节点的值,next 是指向下一个节点的指针/引用。如果要使用双向链表,则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能:

  • get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1。
  • addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。
  • addAtTail(val):将值为 val 的节点追加到链表的最后一个元素。
  • addAtIndex(index,val):在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点。
  • deleteAtIndex(index):如果索引 index 有效,则删除链表中的第 index 个节点。

思路分析

盲猜面试出这个的可能性很大,很考查基础.

示例:

      
      
MyLinkedList linkedList = new MyLinkedList();
linkedList. addAtHead( 1);
linkedList. addAtTail( 3);
linkedList. addAtIndex( 1, 2); //链表变为1-> 2-> 3
linkedList. get( 1); //返回2
linkedList. deleteAtIndex( 1); //现在链表是1-> 3
linkedList. get( 1); //返回3
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.

参考代码

      
      
#include<bits/stdc++.h>
using namespace std;

//很奇怪,按说是可以的...
class MyLinkedList {

public:
//定义链表
struct LinkedNode {
int val;
LinkedNode * next;
LinkedNode(): val( 0), next( NULL) {
};
LinkedNode( int x): val( x), next( NULL) {
};
LinkedNode( int x, LinkedNode * next): val( x), next( next) {
};
};

MyLinkedList() {
head = new LinkedNode();
size = 0;
}
//获取链表中 index 个节点的值。如果索引无效,则返回-1。
int get( int index) {
if( index < 0 || index > size - 1 ) {
return - 1;
}
LinkedNode * cur = head -> next;
while( index --) { //实际上是获得index+1个节点 ,因为index是从0开始的
cur = cur -> next;
}
return cur -> val;
}

// 在链表头部添加节点。
void addAtHead( int val) {
// ListNode *newNode = new ListNode(val,head->next);
// head->next = newNode;
head -> next = new LinkedNode( val, head -> next);
size ++;
}

//链表尾部添加节点
void addAtTail( int val) {
LinkedNode * cur = head;
while( cur -> next) {
cur = cur -> next;
}
cur -> next = new LinkedNode( val);
size ++;
}

//在链表中的第index个节点之前添加值为val 的节点。
//如果index等于链表的长度,则该节点将附加到链表的末尾
//如果 index 大于链表长度,则不会插入节点。
//如果index小于0,则在头部插入节点。

void addAtIndex( int index, int val) {
if( index > size) { //如果 index 大于链表长度,则不会插入节点。
return;
}
if( index < 0) { //如果index小于0,则在头部插入节点。
addAtHead( val);
}
if( index == size) { //如果index等于链表的长度,则该节点将附加到链表的末尾
addAtTail( val);
}
LinkedNode * cur = head;
while( index --) {
cur = cur -> next;
}
cur -> next = new LinkedNode( val, cur -> next);
// ListNode *newNode = new ListNode(val);
// newNode->next = cur->next;
// cur->next = newNode;

size ++;
}

//如果索引 index 有效,则删除链表中的第 index 个节点。
void deleteAtIndex( int index) {
if( index >= size || index < 0) {
return;
}
LinkedNode * cur = head;
while( index --) {
cur = cur -> next;
}
LinkedNode * temp = cur -> next;
cur -> next = cur -> next -> next;
delete temp;
size --;
}
void printLinkedList(){
LinkedNode * cur = head;
while( cur -> next){
cout << cur -> next -> val << " ";
cur = cur -> next;
}
cout << endl;
}
private:
//全局变量
LinkedNode * head;
int size ;


};

int main() {
MyLinkedList * obj = new MyLinkedList();
int param_1 = obj -> get( 0);
cout << param_1 << endl;
obj -> addAtHead( 1);
obj -> printLinkedList();
obj -> addAtTail( 2);
obj -> printLinkedList();
obj -> addAtIndex( 1, 3);
obj -> printLinkedList();
obj -> deleteAtIndex( 0);
obj -> printLinkedList();
return 0;
}
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.
  • 30.
  • 31.
  • 32.
  • 33.
  • 34.
  • 35.
  • 36.
  • 37.
  • 38.
  • 39.
  • 40.
  • 41.
  • 42.
  • 43.
  • 44.
  • 45.
  • 46.
  • 47.
  • 48.
  • 49.
  • 50.
  • 51.
  • 52.
  • 53.
  • 54.
  • 55.
  • 56.
  • 57.
  • 58.
  • 59.
  • 60.
  • 61.
  • 62.
  • 63.
  • 64.
  • 65.
  • 66.
  • 67.
  • 68.
  • 69.
  • 70.
  • 71.
  • 72.
  • 73.
  • 74.
  • 75.
  • 76.
  • 77.
  • 78.
  • 79.
  • 80.
  • 81.
  • 82.
  • 83.
  • 84.
  • 85.
  • 86.
  • 87.
  • 88.
  • 89.
  • 90.
  • 91.
  • 92.
  • 93.
  • 94.
  • 95.
  • 96.
  • 97.
  • 98.
  • 99.
  • 100.
  • 101.
  • 102.
  • 103.
  • 104.
  • 105.
  • 106.
  • 107.
  • 108.
  • 109.
  • 110.
  • 111.
  • 112.
  • 113.
  • 114.
  • 115.
  • 116.
  • 117.
  • 118.
  • 119.
  • 120.
  • 121.
  • 122.
  • 123.
  • 124.

备注:代码本身没啥问题,LeetCode关于这个题可能有点不严谨…


如果有收获!!! 希望老铁们来个三连,点赞、收藏、转发。
创作不易,别忘点个赞,可以让更多的人看到这篇文章,顺便鼓励我写出更好的博客


原网站

版权声明
本文为[51CTO]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_15710480/5451189