链表类型

资料来自代码随想录 (programmercarl.com)

基础知识

链表由数据域和指针域两部分组成,最后一个节点的指针域指向null

  • 单链表:只能单向查询
  • 双链表:每一个节点有两个指针域,一个指向下一个节点,一个指向上一个节点,可以双向查询
  • 循环链表:形成一个环的链表

链表的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class ListNode{
//节点的值
int val;
//下一个节点
ListNode next;
//无参构造器
public ListNode(){

}
//节点的构造函数
public ListNode(int val){
this.val=val;
}
public ListNode(int val,ListNode next){
this.val=val;
this.next=next;
}
}

移除链表的元素

203. 移除链表元素 - 力扣(LeetCode) (leetcode-cn.com)

普通方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public ListNode removeElements(ListNode head, int val) {

while ( head!=null&&head.val==val ){
head=head.next;
}
if(head==null){
return head;
}
ListNode preNode=head;
ListNode curNode=head.next;
while (curNode != null) {
if (curNode.val==val){
preNode.next=curNode.next;
}else {
preNode=curNode;
}
curNode=curNode.next;
}

return head;
}

特殊方法

添加虚拟节点的方式,使得头节点也加入常规之中,规避了头节点为空的复杂情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ListNode removeElements(ListNode head, int val) {
if(head==null){
return head;
}

ListNode dummy=new ListNode(-1,head);
ListNode preNode=dummy;
ListNode curNode=head;
while (curNode != null) {
if (curNode.val==val){
preNode.next=curNode.next;
}else {
preNode=curNode;
}
curNode=curNode.next;
}
//在这里返回dummy.next;是因为上面的方法中头节点在一直改变,head所代表的节点在一直发生改变,在这里可能原来的head.val==val,head已经消失了
return dummy.next;
}

其他题目

https://moonshuo.cn/posts/54869.html

链表相交

面试题 02.07. 链表相交 - 力扣(LeetCode)

普通方法

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
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode tempA = headA;

//用于存储相交的节点
while (tempA != null) {
ListNode tempB = headB;
while (tempB != null) {
if (tempA == tempB) {
return tempA;
} else {
if (tempB.next != null) {
tempB = tempB.next;
} else {
break;
}
}
}
if (tempA.next != null) {
tempA = tempA.next;
} else {
return null;
}
}
return 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
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
HashSet<ListNode> hashSet = new HashSet<>();
ListNode tempA = headA;
while (tempA != null) {
hashSet.add(tempA);
if (tempA.next != null) {
tempA = tempA.next;
} else {
break;
}
}
ListNode tempB = headB;
while (tempB != null) {
if (!hashSet.add(tempB)) {
return tempB;
} else {
if (tempB.next != null) {
tempB = tempB.next;
}else {
break;
}
}
}
return null;
}

双指针方法

这个双指针非常巧妙的经过依次调换之后,将两个指针指到了相交节点前的相同的位置,简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
/*
总体思路:双指针
headA=[a1,a2,...,an]与headB=[b1,b2,...,bn]
pA在a1出发,pB在b1出发;当pA到达A链表末尾null就到B开头处重新开始;pB同理
最后两个指针相遇时就是相交的地方
*/
ListNode pA = headA, pB = headB;
while (pA != pB) {
// A指针与B一路往下走,走完了就去另一个链表的头结点,直至相遇
// 这里注意不能用pA.next作为判断,因为遇到空链表会发生空指针异常
// 这里就算有其中一个链表为空或者没相交的也成立(最后为null)
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
// pA==pB
return pA;
}

判断环形链表

142. 环形链表 II - 力扣(LeetCode)

普通方法

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
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
HashSet<ListNode> listNodes=new HashSet<>();

ListNode temp=head;
while (temp!=null){
if (!listNodes.add(temp)){
return temp;
}else {
temp=temp.next;
}

}
return 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
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
ListNode slow = head, fast = head;
while (fast != null) {
slow = slow.next;
if (fast.next != null) {
fast = fast.next.next;
} else {
return null;
}
if (fast == slow) {
ListNode ptr = head;
while (ptr != slow) {
ptr = ptr.next;
slow = slow.next;
}
return ptr;
}
}
return null;
}
}