leetCode- - - 链表

目录

1.反转链表（leetcode206）

2. 链表内指定区间反转（leetcode92）

3.链表中的节点每k个一组翻转（leetcode25）

4.合并两个排序的链表（leetcode21）

5.链表的中间节点（leetcode876）

6.重排链表（leetcode143）

7.旋转链表（leetcode61）

8.删除排序链表中的重复元素（leetcode83）

9.删除排序链表中的重复元素（LeetCode 82）（迭代版）

10.环形链表 II （ LeetCode 142 ）

11.回文链表（ LeetCode 234 ）

12.相交链表（ LeetCode 160 ）

13.奇偶链表（ LeetCode 328 ）

14.移除链表元素（ LeetCode 203 ）

15.链表题目做题总结

---

1.反转链表（leetcode206）

import java.util.*;/** public class ListNode {*   int val;*   ListNode next = null;*   public ListNode(int val) {*     this.val = val;*   }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param head ListNode类 * @return ListNode类*/public ListNode ReverseList (ListNode head) {// write code hereListNode prev=null;ListNode cur=head;if(head==null){return null;}if(head.next==null){return head;}while(cur!=null){ListNode temp=cur.next;cur.next=prev;prev=cur;cur=temp;}return prev;}
}

2. 链表内指定区间反转（leetcode92）

import java.util.*;/** public class ListNode {*   int val;*   ListNode next = null;*   public ListNode(int val) {*     this.val = val;*   }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类*/public ListNode reverseBetween (ListNode head, int m, int n) {// write code hereListNode dummy=new ListNode(0);dummy.next=head;ListNode prev=dummy;for(int i=0;i<m-1;i++){prev=prev.next;}ListNode cur=prev.next;for(int i=0;i<n-m;i++){ListNode temp=cur.next;cur.next=temp.next;temp.next=prev.next;prev.next=temp;}return dummy.next;}
}

3.链表中的节点每k个一组翻转（leetcode25）

public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param head ListNode类* @param k int整型* @return ListNode类*/public ListNode reverseKeyGroup (ListNode head, int k) {// write code hereListNode tail=head;//1.递归结束的点for (int i = 0; i < k; i++) {if(tail==null){return head;}tail=tail.next;}//2.完成每k个元素内的翻转ListNode prev=null;ListNode cur=head;while (cur!=tail){ListNode temp=cur.next;cur.next=prev;prev=cur;cur=temp;}head.next=reverseKeyGroup(tail,k);return prev;}
}

4.合并两个排序的链表（leetcode21）

import java.util.*;/** public class ListNode {*   int val;*   ListNode next = null;*   public ListNode(int val) {*     this.val = val;*   }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pHead1 ListNode类 * @param pHead2 ListNode类 * @return ListNode类*/public ListNode Merge (ListNode pHead1, ListNode pHead2) {// write code hereListNode dummy =new ListNode(-1);ListNode prev=dummy;while(pHead1!=null && pHead2!=null){if(pHead1.val<pHead2.val){prev.next=pHead1;pHead1=pHead1.next;prev=prev.next;}else{prev.next=pHead2;pHead2=pHead2.next;prev=prev.next;}}if(pHead1!=null){prev.next=pHead1;}if(pHead2!=null){prev.next=pHead2;}return dummy.next;}
}

5.链表的中间节点（leetcode876）

解题：快慢指针

class Solution {public ListNode middleNode(ListNode head) {ListNode fast=head;ListNode slow=head;while(fast!=null && fast.next!=null){slow=slow.next;fast=fast.next.next;}return slow;}
}

6.重排链表（leetcode143）

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

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

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public void reorderList(ListNode head) {//1.快慢指针找到中间节点，分成左右两个链表ListNode leftHead=head;ListNode mid=midNode(head);ListNode rightHead=mid.next;//断开左右两个链表mid.next=null;//2.反转右边的链表rightHead=reverse(rightHead);//3.交错合并左右链表while(leftHead!=null && rightHead!=null){ListNode leftHeadNext=leftHead.next;ListNode rightHeadNext=rightHead.next;leftHead.next=rightHead;leftHead=leftHeadNext;rightHead.next=leftHead;rightHead=rightHeadNext;}}public ListNode midNode(ListNode head){ListNode slow=head;ListNode fast=head;while(fast!=null && fast.next!=null){fast=fast.next.next;slow=slow.next;}return slow;}public ListNode reverse(ListNode head){ListNode prev=null;ListNode cur=head;if(head==null){return null;}if(head.next==null){return head;}while(cur!=null){ListNode temp=cur.next;cur.next=prev;prev=cur;cur=temp;}return prev;}
}

7.旋转链表（leetcode61）

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode rotateRight(ListNode head, int k) {if(head==null || k==0){return head;}//计算出链表的长度，当k非常大时，走k步等于走k%len步ListNode cur=head;int len=0;while(cur!=null){len+=1;cur=cur.next;}k=k%len;//former指针先走k步ListNode former=head;ListNode later=head;for(int i=0;i<k;i++){former=former.next;}while(former.next!=null){former=former.next;later=later.next;}former.next=head;ListNode newHead=later.next;later.next=null;return newHead;}
}

8.删除排序链表中的重复元素（leetcode83）

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

class Solution {public ListNode deleteDuplicates(ListNode head) {ListNode cur=head;if(head==null || head.next==null){return head;}while(cur!=null && cur.next!=null){if(cur.val==cur.next.val){cur.next=cur.next.next;}else{cur=cur.next;}}return head;}

9.删除排序链表中的重复元素（LeetCode 82）（迭代版）

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

也可以使用递归的方式，个人认为迭代的方式更容易理解。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode deleteDuplicates(ListNode head) {ListNode dummy=new ListNode(-1);dummy.next=head;ListNode cur=dummy;while(cur.next!=null && cur.next.next!=null){if(cur.next.val==cur.next.next.val){int value=cur.next.val;while(cur.next!=null && cur.next.val==value){cur.next=cur.next.next;}}else{cur=cur.next;}}return dummy.next;}
}

10.环形链表 II （ LeetCode 142 ）

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

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

不允许修改 链表。

/*** 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) {ListNode fast=head;ListNode slow=head;while(fast!=null && fast.next!=null){fast=fast.next.next;slow=slow.next;if(fast==slow){ListNode b=fast;ListNode a=head;while(a!=b){a=a.next;b=b.next;}return a;}}return null;}
}

11.回文链表（ LeetCode 234 ）

给你一个单链表的头节点 head ，请你判断该链表是否为

回文链表

。如果是，返回 true ；否则，返回 false 。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public boolean isPalindrome(ListNode head) {if(head.next==null){return true;}if(head.next.next==null){if(head.val==head.next.val){return true;}else{return false;}}//1.找到中间节点ListNode fast=head;ListNode slow=head;while(fast.next!=null && fast.next.next!=null){fast=fast.next.next;slow=slow.next;}//2.分割为两个链表ListNode leftHead=head;ListNode rightHead=slow.next;//3.反转右边链表rightHead= reverse(rightHead);//4.比较左右链表while (rightHead!=null){if(leftHead.val==rightHead.val){leftHead=leftHead.next;rightHead=rightHead.next;}else{return false;}}return true;}public ListNode reverse(ListNode head){ListNode pre=null;ListNode cur=head;while(cur!=null){ListNode temp=cur.next;cur.next=pre;pre=cur;cur=temp;}return pre;}
}

12.相交链表（ LeetCode 160 ）

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

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

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

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

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode pa=headA;ListNode pb=headB;if(headA==null || headB==null){return null;}while(pa!=pb){if(pa==null){pa=headB;}else{pa=pa.next;}if(pb==null){pb=headA;}else{pb=pb.next;}}return pa;}
}

13.奇偶链表（ LeetCode 328 ）

给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。

请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode oddEvenList(ListNode head) {//链表为空或者只有一个节点，直接返回即可if(head==null || head.next==null){return head;}ListNode odd=head;ListNode even=odd.next;ListNode evenHead=even;while(even!=null && even.next!=null){odd.next=even.next;    odd=odd.next;even.next=odd.next;even=even.next;}odd.next=evenHead;return head;}
}

14.移除链表元素（ LeetCode 203 ）

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

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode removeElements(ListNode head, int val) {if(head==null){return null;}ListNode dummy=new ListNode(-1);dummy.next=head;ListNode pre=dummy;ListNode cur=head;while(cur!=null){if(cur.val==val){pre.next=cur.next;}else{pre=cur;}cur=cur.next;}return dummy.next;}
}

15.链表题目做题总结

1.画图理清思路。
2.考虑边界条件：链表问题通常有很多边界条件需要考虑，例如空链表、只有一个节点的链表、链表长度为偶数或奇数等等。
3.双指针技巧

   快慢指针：用于找链表中点、检测环等问题。
   双指针一前一后：用于逆转链表、找倒数第k个节点等问题。
   双指针同向移动：用于合并两个有序链表等问题。
4.递归的应用：
   有些链表问题可以通过递归来简化处理，例如逆转链表、检测回文链表等。
5.注意内存管理：
   如果涉及到链表节点的删除或插入，要确保不会造成内存泄漏或者指针丢失。特别是在删除节点时，要注意处理好被删除节点的前驱和后继节点的指针关系。
6.利用哨兵节点简化操作：
   在一些操作中，使用哨兵节点（dummy node）可以简化边界条件的处理，特别是在涉及头节点操作时特别有效。