链表可是很重要的知识,是面试时常考的知识点,这次让我们系统的学习一下吧

文章目录

• 1. 链表的定义
• 2. 链表的创建
• • 2.1 基础创建
  • 2.2 尾插法创建头节点
  • 2.3 头插法
• 3. 链表的基础方法
• • 3.1 获取链表长度
  • 3.2 是否包含某个节点
  • 3.3 在任意坐标处插入节点
  • 3.4 删除第一个值为key的节点
  • 3.5 删除所有节点值为key的节点
• 4. 链表的进阶方法
• • 4.1 反转链表
  • 4.2 找出中间节点
  • 4.3 找出倒数第K个节点
  • 4.4 用数值x分割列表
  • 4.5 判断是否为回文链表
  • 4.6 判断链表是否有环
  • • 1. 附加 给链表添加环
  • 4.7 找出环的入口

1. 链表的定义

链表有几种常见类型,单向循环带头节点,单向循环不带头结点,单项非循环带头节点,单向非循环不带头结点,双向循环带头结点…
这里,我们只讲最重要最常考的两个==,双向非循环不带头结点和单项非循环不带头结点.==
一个链表就像火车一样,由一个个节点串起来,每个节点都要标出节点值和它的下一个节点的物理位置(next),之后再一次连接,就组成了链表.
如下图,链表的一个节点由节点值val和它的下一节点的位置组成

如下图是一个单向不循环无头结点的链表.链表的第一个节点,0x21是节点自身位置,12是节点值,0x39是下一个节点的位置,也就是第二个节点的位置.

链表的空间顺序,逻辑上是连续的,物理上是随机的.
而顺序表ArrayList物理上是连续存储的一块空间.

2. 链表的创建

2.1 基础创建

1.我们先简单创建一个链表,熟悉一下链表的使用,注意结尾处的this.head = listnode1,指定第一个节点为链表头节点.

 	public void createList(){ListNode listnode1 = new ListNode(12);ListNode listnode2 = new ListNode(25);ListNode listnode3 = new ListNode(3);ListNode listnode4 = new ListNode(79);ListNode listnode5 = new ListNode(53);listnode1.next = listnode2;listnode2.next = listnode3;listnode3.next = listnode4;listnode4.next = listnode5;listnode5.next = null;this.head = listnode1;}

2.2 尾插法创建头节点

尾插法就是把新节点插到链表的末尾.
如下图所示,要求插入新的节点,节点值为99.

首先,我们要讨论一种特殊情况,就是链表还没有节点,那么头节点就是这个插入的新节点.

ListNode listnode = new ListNode(data);
if(head == null){head = listnode;
}

若是节点有头节点,则就遍历链表,找到链表尾巴,把新节点插到尾巴后面即可.
那么怎么找到链表的尾巴呢,从那面那幅图我们看到,链表尾巴的next为null,所以从头开始遍历,直到节点的next为null.就把新节点插到这个节点后面.

			ListNode cur = head;while(cur.next != null){cur = cur.next;}cur.next = listnode;

完整代码如下

	public void addLast(int data){ListNode listnode = new ListNode(data);if(head == null){head = listnode;}else{ListNode cur = head;while(cur.next != null){cur = cur.next;}cur.next = listnode;listnode.next = null;}}

执行结果为

2.3 头插法

如下图,把节点值为99的节点插在链表头部,即node.next = head;head改为node,这里没有解引用,不用判断head == null.

	public void addFirst(int data){ListNode node = new ListNode(data);node.next = head;head = node;}

3. 链表的基础方法

3.1 获取链表长度

遍历一遍链表,从head开始,注意结束位置,是cur != null,注意别落下那个cur.next == null的最后一个节点.

	public int size(){int count = 0;ListNode cur = head;while(cur != null){count++;cur = cur.next;}return count;}

3.2 是否包含某个节点

注意循环条件,cur != null

	public boolean contain(int key){ListNode cur = this.head;while(cur != null){if(cur.val == key){return true;}cur = cur.next;}return false;}

3.3 在任意坐标处插入节点

为了保证程序在遇到不合法的输入时崩溃,我们在启动程序之前就要考虑好所有可能输入值会出现的结果.
void addIndex(int index, int value)
首先,若是选定的坐标小于0,或者超出给定范围,程序要报错,防止程序崩溃.

		if(index < 0 || index > size()){throw new WrongIndexException("选择的坐标不合法");}

其次,当给定坐标是0时,头插此节点,给定坐标是size()时,尾插此节点

	   if(index == 0){addFirst(value);}else if(index == size()){addLast(value);}

若都不是,如下图,在坐标1处插入值为100的节点.

这里就要修改99的next指向和100的next指向.也就是找到坐标处的前一个位置cur,如下图
注意这里我们不可以先修改cur的next,如下代码,如果先修改cur的next,node的next就找不到了.

cur.next = node;
node.next = cur.next

正确的写法如下

node.next = cur.next;
cur.next = node;

完整代码如下

	public void addIndex(int index,int value){if(index < 0 || index > size()){throw new WrongIndexException("选择的坐标不合法");}if(index == 0){addFirst(value);}else if(index == size()){addLast(value);}else{ListNode cur = head;while((index-1) > 0){cur = cur.next;index--;}ListNode node = new ListNode(value);node.next = cur.next;cur.next = node;}}

3.4 删除第一个值为key的节点

首先,我们需要找到值为key的节点的前一个结点,改变这个节点的next指向,就可以删除值为key的节点.
这里要考虑几个特殊情况
1.head 为 null,链表为空链表,直接返回

		if (head == null) {System.out.println("链表为空链表,无法删除");return;}

2.我们遍历的节点值,是从head.next开始的,所以要特别关注一下head的值是不是key,head.val 为key,直接head = head.next;

		ListNode cur = head;//如果头节点的值 == keyif(cur.val == key){head = head.next;return;}

之后,正常找,找到值为key的节点的前一个结点.

		while (cur.next != null) {if (cur.next.val == key) {break;}cur = cur.next;}

如果遍历完毕,找到了,修改前一个结点的next指向,没找到,直接返回

		if(cur.next != null){//正常找到,改变cur的next指向即可cur.next = cur.next.next;}else{               System.out.println("未找到要删除的节点");//没找到节点,直接返回return;}

完整代码如下

	public void deleteKey(int key) {if (head == null) {System.out.println("链表为空链表,无法删除");return;}ListNode cur = head;//如果头节点的值 == keyif(cur.val == key){head = head.next;return;}//找到值为key的节点的前一个结点,找到后退出循环while (cur.next != null) {if (cur.next.val == key) {break;}cur = cur.next;}//如果刚好是最后一个节点值为key,删除最后一个节点,即改变preCur的next指向if(cur.next != null){//正常找到,改变cur的next指向即可cur.next = cur.next.next;}else{               System.out.println("未找到要删除的节点");//没找到节点,直接返回return;}}

3.5 删除所有节点值为key的节点

这道题有点难想,我们需要找到每一个节点为key的节点的前一个结点,改变节点的next指向,进而删除节点.
如下图,删除所有值为12的节点.从第二个节点开始遍历,若是cur的值为key,便修改preCur的next指向.否则,cur和preCur往后走.

第二个节点值不为key,cur,preCur往后走.如下图

cur的值为key,便通过修改preCur的next指向来删除第三个节点.preCur.next = cur.next;cur向后移动.注意这里preCur是记录链表cur节点的前一个节点,所以这里preCur不用变.

 			if(cur.val == key){preCur.next = cur.next;cur = cur.next;}

如下图

之后的操作重复,不做赘述.
最后,注意我们还没比较头节点的值是不是key,如果符合的话,直接head == head.next;

		 if(head.val == key){head = head.next;}

完整代码如下.

	public void deleteAllKey(int key){if(head == null){System.out.println("链表为空链表");return;}ListNode cur = head.next;ListNode preCur = head;while(cur != null){if(cur.val == key){preCur.next = cur.next;cur = cur.next;}else{preCur = cur;cur = cur.next;}}if(head.val == key){head = head.next;}}

4. 链表的进阶方法

4.1 反转链表

如下图所示,将链表反转

思路是使后一节点的next指向前一节点,但要事先保留后一节点的next节点.
先考虑两个特殊情况,空链表和只有一个节点的链表直接返回就可.

		if(head == null){return ;}if(head.next == null){return ;}

定义cur = head.next,preCur = head,nextCur = cur.next;如下图

修改第二个节点指向

		    nextCur = cur.next;cur.next = preCur;preCur = cur;cur = nextCur;

如下图,修完完第二个节点的next指向,cur = nextCur.一定要事先记录好cur的原next节点.

之后,再次进入循环,记录完cur的next节点后,修改cur的next指向.
最后全部修改完毕,如下图注意处理头节点和尾节点.
原头节点12的next置为空,之后head 改为preCur

完整代码如下

	public void reverseList(){if(head == null){return ;}if(head.next == null){return ;}ListNode preCur = head;ListNode cur = head.next;ListNode nextCur = null;while(cur != null){nextCur = cur.next;cur.next = preCur;preCur = cur;cur = nextCur;}head.next = null;head = preCur;}

执行结果如下

4.2 找出中间节点

这个我们通过快慢节点的方法找出中间节点.快节点一次走两步,慢节点一次走一步,快节点走到终点的时候,列出方程,2x = s,x = s/2,则慢节点走到了中间位置.
首先,如果是空链表或者是只有一个节点,直接返回head即可.

		if(head == null){System.out.println("链表为空链表");return null;}if(head.next == null){return head;}

之后,快慢节点往后走,直到fast.next = null.

		while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;}

如下图,slow节点就是中间节点.

完整代码如下

 	public ListNode getMidNode(){if(head == null){System.out.println("链表为空链表");return null;}if(head.next == null){return head;}ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;}return slow;}

执行结果为

4.3 找出倒数第K个节点

用的方法也是快慢节点,快节点先走K-1步,之后快慢节点一起走,快节点走到终点,慢节点就到了倒数第K个节点.
如下图,找倒数第4个节点,快节点先走3步

之后,快慢节点一起走,直到快节点走到终点,慢节点就是倒数第四个节点.

首先讨论特殊情况
1.链表为空链表,直接返回null
2.K非法,小于0,或者大于链表的size().需要抛出异常.

		if(head == null){return null;}if(k < 0 || k > this.size()){throw new WrongIndexException("输入的坐标非法");}

正常情况,fast先走K-1,之后fast,slow一起走

	ListNode fast = head;ListNode slow = head;while(k-1 > 0){fast = fast.next;k--;}while(fast.next != null){fast = fast.next;slow = slow.next;}

完整代码如下

public ListNode LastKthNode(int k){if(head == null){return null;}if(k < 0 || k > this.size()){throw new WrongIndexException("输入的坐标非法");}ListNode fast = head;ListNode slow = head;while(k-1 > 0){fast = fast.next;k--;}while(fast.next != null){fast = fast.next;slow = slow.next;}return slow;}

4.4 用数值x分割列表

链表小于数x的节点放左边,大于x的节点放右边,节点相对顺序要求保持不变.
如下图,要求节点值小于30的节点放左边,节点值大于30的节点放右边.保持相对位置不变,例如第二个链表中,54要在44的前面,这个相对位置不能变.

这里我们需要实现两个链表,第一个链表装小于30的节点,第二个链表装大于30的节点,最后再将两个链表连起来,就可以啦~
所以呢,我们这里要准备第一个节点的尾节点be和第二个节点的头节点as,用于两个链表的连接.准备第一个链表的头节点,用于新链表的遍历,准备第二个节点的尾节点,给他的next置空.如下图所示.

首先,找到第一个小于30的节点,作为链表1的头节点bs,之后小于30的节点往后连.

		 if(cur.val < x){if(bs == null){bs = cur;be = cur;}else{be.next = cur;be = be.next;}}

找到第一个大于30的节点,作为链表2的头节点,之后大于30的节点往后连.

			else{if(as == null){as = cur;ae = cur;}else{ae.next = cur;ae = ae.next;}}

最后将这两个链表连起来.
这里要考虑一个特殊情况,原链表里如果没有小于30的节点,bs = null,直接返回as就行,记得要把ae的next置空.

		if(bs == null){if(ae != null){ae.next = null;}return as;}

正常情况直接连就可以.

		else{be.next = as;if(ae != null){ae.next = null;}return bs;}

完整代码如下

	public ListNode seperateList(int x){ListNode bs = null;ListNode be = null;ListNode as = null;ListNode ae = null;ListNode cur = head;while(cur != null){if(cur.val < x){if(bs == null){bs = cur;be = cur;}else{be.next = cur;be = be.next;}}else{if(as == null){as = cur;ae = cur;}else{ae.next = cur;ae = ae.next;}}cur = cur.next;}if(bs == null){if(ae != null){ae.next = null;}return as;}else{be.next = as;if(ae != null){ae.next = null;}return bs;}}

4.5 判断是否为回文链表

如下图,两个链表都为回文链表.

如何判断链表是否是回文链表呢?
我们可以发现,回文链表的首尾节点到中间节点的值一直是相同的.我们首先找到中间节点,反转后面的链表,如下图,我们从头节点和尾节点向中间遍历,如果节点值一直相同,则为回文链表,否则不是.

找到中间节点,之前的代码说过这个,用什么方法来着?---------------------------快慢指针,slow为中间节点.

		ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;}

反转中间节点之后的链表

		ListNode cur = slow.next;ListNode preCur = slow;while(cur != null){ListNode curNext = cur.next;cur.next = preCur;preCur = cur;cur = curNext;}

被反转后的链表如下图.

这里的preCur就是尾节点了.
之后从首尾向中间遍历节点,值不同返回false,直到首尾节点都走到了中间节点或者preCur.next = head,循环结束.

		while(preCur != head){if(preCur.val != head.val){return false;}if(preCur.next == head){return true;}preCur = preCur.next;head = head.next;}return false;

完整代码

	public boolean palindromeLinkedList(){if(head == null){return false;}if(head.next == null){return true;}ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;}ListNode cur = slow.next;ListNode preCur = slow;while(cur != null){ListNode curNext = cur.next;cur.next = preCur;preCur = cur;cur = curNext;}while(preCur != head){if(preCur.val != head.val){return false;}if(preCur.next == head){return true;}preCur = preCur.next;head = head.next;}return false;}

4.6 判断链表是否有环

如下图,链表最后一个节点指向前面的某个节点,则链表中出现了环.

如何判断链表是否有环呢?
我们采用快慢指针的方法,由于链表中有环,一个走两步,一个走一步,两个指针总会指向同一个节点.
完整代码如下.

	public boolean linkedListHasRing(){ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if(fast == slow){return true;}}return false;}

1. 附加 给链表添加环

最后一个节点的next指向前面的某个节点.

	public void createRing(){ListNode cur = head;while(cur.next != null){cur = cur.next;}cur.next = head.next;}

4.7 找出环的入口

这里用到了数学里的解方程,如下图,
慢指针的路程*2 = 快指针的路程
推导出:头节点到环入口的距离 = 相遇点到环入口的距离

所以,先找到相遇点,让指针分别从头节点和相遇点往中间走,直到两指针相遇,相遇的点就是环的入口.

找到相遇点

		ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if(fast == slow){break;}}

如果链表没环,循环是不符合循环条件,自然跳出来的

		if(fast == null || fast.next == null){return null;}

链表有环的话,让两个指针从头节点和相遇点往中间走,相遇的点为环的入口.

		ListNode cur = head;while(cur != slow){cur = cur.next;slow = slow = slow.next;}return cur;

完整代码

	public ListNode inletOfRing(){ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null){fast = fast.next.next;slow = slow.next;if(fast == slow){break;}}if(fast == null || fast.next == null){return null;}ListNode cur = head;while(cur != slow){cur = cur.next;slow = slow = slow.next;}return cur;}