前言
链表类型的习题常用的技巧就是定义指针来代替head的，替head走，要么就是数学问题，环形链表就是利用数学思想取解决的，要么就是定义双指针来操作链表。
一、删除链表中给定值为key的节点
定义两个变量，一个使待删除的节点，一个为待删除节点的前驱节点，最后记得判断头节点是否为要删除的节点，最后返回头节点。
|
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 null; } ListNode cur=head.next; ListNode prev=head; while(cur!=null){ if(cur.val==val){ prev.next=cur.next; }else{ prev=cur; } cur=cur.next; } if(head.val==val){ head=head.next; } return head; } |
二、反转链表
定义双指针法，类似于头插法，来将链表的节点头插法
cur节点是待反转的节点 curNext是保存下一个节点的地址值
1.先保存待反转节点下一个地址值，之后将头节点的next置空
2.只有用头插法将节点头插即可。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
public ListNode reverseList(ListNode head) { //三指针法来反转链表 if(head==null||head.next==null){ return head; } ListNode cur=head;//要头插的节点 ListNode curNext=head.next;//保存下一个节点的地址值 cur=curNext; head.next=null; while(cur!=null){ curNext=curNext.next; cur.next=head; head=cur; cur=curNext; } return head; } |
三、返回链表的中间节点
定义快慢指针，注意偶数节点和奇数节点的情况
注意判断条件 在偶数情况下 如果是判断fast.next.next就会空指针异常，必须把判断条件两个都加上。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
public ListNode middleNode(ListNode head) { //定义快慢指针 快指针比慢指针多走一步 注意奇数和偶数情况 if(head==null||head.next==null){ return head; } ListNode slow=head; ListNode fast=head; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; } return slow; } |
四、删除链表的倒数第K个节点
定义快慢指针 快指针先走n-1步 之后慢指针再走,修改地址值即可
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
public ListNode removeNthFromEnd(ListNode head, int n) { if(head==null){ return null; } ListNode fast=head; ListNode dummy=new ListNode(0,head); ListNode slow=dummy; for(int i=1;i<n;i++){ fast=fast.next; } while(fast.next!=null){ fast=fast.next; slow=slow.next; } slow.next=slow.next.next; return dummy.next; } |
五、分割链表
给定X值，分割链表 前面链表为小于X的值，后面链表为大于等于X的值
要考虑很多情况
1.第一次插入链表时 要将头节点和尾巴节点都指向插入的节点
2.不是第一次插入时，只需要把尾巴节点next值指向插入的节点，之后把尾巴节点往后挪
3.如果前面链表为空，返回后面链表的头
4。还需要将后面节点的next值置空，之后连接两个链表。
|
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
|
public ListNode partition(ListNode head, int x) { //分割链表 将小于x的分为一部分，将大于等于x的分为一部分呢！ 乖乖yy if(head==null){ return null; } ListNode xh=null;//小于x的头节点 ListNode xe=null;;//小于x的尾巴节点 ListNode Xh=null;//大于等于X的头节点 ListNode Xe=null;//大于等于X的尾节点 ListNode cur=head; while(cur!=null){ if(cur.val<x){ //小于X的部分 if(xh==null){ //第一次插入 xh=cur; xe=cur; }else{ //不是第一次插入 xe.next=cur; xe=cur; } }else{ //>=X 的部分 if(Xh==null){ //第一次插入 Xh=cur; Xe=cur; }else{ //不是第一次插入 Xe.next=cur; Xe=cur; } } cur=cur.next; }//判断 所有元素都大于x 前面的链表没有数据 要返回后面的链表 if(xh==null){ return Xh; } xe.next=Xh; if(Xh!=null){ //将最后一个元素置为null Xe.next=null; } return xh; } |
六、合并两个有序链表
和合并有序数组是一样的，链表复杂一些要将后面节点地址先保存，之后定义傀儡节点，按照值小的顺序连接起来
|
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
|
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { //1.思路就是先定傀儡节点，将链表穿起来 定义两个变量将后面地址保存起来 之后串糖葫芦一样串起来 ListNode dummy=new ListNode(-1); ListNode head=dummy;//保存傀儡节点 ListNode cur1=l1;//保存节点后面的地址值 ListNode cur2=l2; while(l1!=null&&l2!=null){ cur1=l1.next; cur2=l2.next; if(l1.val<=l2.val){ dummy.next=l1; l1=cur1; }else{ dummy.next=l2; l2=cur2; } dummy=dummy.next; } if(l1!=null){ dummy.next=l1; } if(l2!=null){ dummy.next=l2; } return head.next; } |
七、删除有序链表中重复节点
双指针 遇到相等的就跳过 ，最后要将最后一个节点置为空。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public ListNode deleteDuplicates(ListNode head) { if(head==null){ return null; } ListNode prev=head; ListNode cur=head.next; while(cur!=null){ if(prev.val==cur.val){ cur=cur.next; }else{ prev.next=cur; prev=cur; cur=cur.next; } } prev.next=cur; return head; } |
八、环形链表
先用set判断是否存在 空间复杂度为O（N），不太符合题目要求
|
1
2
3
4
5
6
7
8
9
10
11
|
public boolean hasCycle(ListNode head) { HashSet<ListNode> set=new HashSet<>(); while(head!=null){ set.add(head); head=head.next; if(set.contains(head)){ return true; } } return false; } |
2.快慢指针数学问题，快指针走两步，慢指针走一步，有环一定相遇，没有环就不会相遇 空间复杂度为O(1)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public boolean hasCycle(ListNode head) { //快慢指针还是数学问题 if(head==null||head.next==null){ return false; } ListNode slow=head; ListNode fast=head.next; while(slow!=fast){ if(fast==null||fast.next==null){ return false; } fast=fast.next.next; slow=slow.next; } return true; } |
九、相交链表
1.先利用set存储节点 之后循环判断，空间复杂度为O（N）时间复杂度为O（N），比较慢
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { HashSet<ListNode>set=new HashSet<>(); while(headA!=null){ set.add(headA); headA=headA.next; } while(headB!=null){ if(set.contains(headB)){ return headB; } headB=headB.next; } return null; } |
2.双指针，确实没想出来，看了题解才知道是两个链表相连接，遍历是否有想交的节点
|
1
2
3
4
5
6
7
8
9
|
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode cur1=headA; ListNode cur2=headB; while(cur1!=cur2){ cur1=cur1==null?headB:cur1.next; cur2=cur2==null?headA:cur2.next; } return cur1; } |
十、两数相加
这道题没什么技巧，就是注意很多特殊情况，加完要判断进位，我第一次敲的时候能执行但是不能过，没有考虑到特殊情况。
最后看评论解答就是用一个进位标志数来解决，学到了。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode list=new ListNode(-1); ListNode head=list; int t=0; while(l1!=null||l2!=null||t!=0){ if(l1!=null){ t+=l1.val; l1=l1.next; } if(l2!=null){ t+=l2.val; l2=l2.next; } list.next=new ListNode(t%10); list=list.next; t/=10; } return head.next; } |
十一、回文链表
1.可以将链表中值存放在顺序表中，之后定义双指针遍历判断
2.快慢指针带反转
3.利用栈实现li
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
public boolean isPalindrome(ListNode head) { //利用栈来实现回文结构 Stack<Integer> stack=new Stack<>(); ListNode cur=head; while(cur!=null){ stack.push(cur.val); cur=cur.next; } ListNode cur1=head; while(cur1!=null){ if(cur1.val!=stack.pop()){ return false; } cur1=cur1.next; } return true; } |
定义快慢指针，之后反转链表来实现
|
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
|
public boolean isPalindrome(ListNode head) { //快慢指针来反转链表 if(head==null||head.next==null){ return true; } ListNode fast=head; ListNode slow=head; while(fast.next!=null&&fast.next.next!=null){ fast=fast.next.next; slow=slow.next; } //走到中间节点，反转链表 slow=reverse(slow.next); while(slow!=null){ if(head.val!=slow.val){ return false; } head=head.next; slow=slow.next; } return true; } public ListNode reverse(ListNode head){ //反转链表 ListNode cur=head; ListNode curNext=head.next; cur=curNext; head.next=null; while(cur!=null){ curNext=curNext.next; cur.next=head; head=cur; cur=curNext; } return head; } |
总结
本篇文章就到这里了，希望能给你带来帮助，也希望你能给多多关注服务器之家的更多内容！
原文链接：https://blog.csdn.net/weixin_51601437/article/details/118188678
