删除链表中等于给定值 val 的所有节点
给你一个链表的头节点 head 和一个整数 val
请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点
例如：
- 力扣链接: 删除链表中等于给定值 val 的所有节点
想要做好题，就要先理解力扣给得参数，看下图：
力扣上传了二个参数过来：
head 代表链表的头节点
val 代表要删除的元素
题解：
创建二个变量，cur 赋值 head.next ，它指向 head 引用的地址，prev 赋值 head,它指向 head
cur 用来判断当前需要删除的节点
prev 代表当前需要删除节点的前一个节点
源题代码：
class Solution {
public ListNode removeElements(ListNode head, int val) {
//判断链表是否为空链表
if(head == null){
return null;
}
ListNode cur = head.next;//cur 存储的是 head 下一个节点地址
ListNode prev = head; // perv 指向 head 头节点
while(cur != null){
// 判断 cur 所在节点的值是否等于 val 元素
if(cur.val == val){
prev.next = cur.next;
cur = cur.next;
}else{
prev = cur;
cur = cur.next;
}
}
// 判断第一个节点是否等于 val 值
if(head.val == val){
head = head.next;
}
// 返回新的节点
return head;
}
}
反转链表
给你一个单链表的头节点 head ，请你反转链表，并返回反转后的链表
- 力扣链接: 反转链表
力扣上传了一个参数过来：
head 代表链表的头节点
题解：
最先判断传过来的参数是否为 null ，之后判断传过来的链表是否是只有一个节点
如果只有一个节点直接返回不用反转
接下来就是先把头节点制为 null ，之后是修改节点的指向
源题代码：
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null){
return null;
}
if(head.next == null){
return head;
}
ListNode cur = head.next;
head.next = null;
while(cur != null){
ListNode curNext = cur.next;
cur.next = head;
head = cur;
cur = curNext;
}
return head;
}
}
链表的中间结点
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
示范1：
链表元素：1 2 3 4 5
其中间元素是： 3
示范2：
链表元素：1 2 3 4 5
其中间元素是： 3 和 4 返回第二个元素 4
- 力扣链接: 链表的中间结点
传过来的参数head是头节点
题解：
这题可以使用快慢指针来解决
快慢指针：A和B二个变量同时出发，A的速度是B的二倍，当A到达终点时，B的位置就在中间位置
这有二种情况：偶数和奇数
奇数：一次走二步最后肯定是走到末尾的，判断条件是 A.next != null
偶数：一次走二步最后走到的是末尾后一个元素位置，判断条件是 A != null
判断的顺序是：偶数在奇数
源题代码：
class Solution {
public ListNode middleNode(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
// fast.next.next 是下一个节点的下一个节点
fast = fast.next.next;
slow = slow.next;
}
//返回中间节点
return slow;
}
}
链表中倒数第k个结点
输入一个链表，输出该链表中倒数第k个结点。
示例1：
链表：1 2 3 4 5
找倒数第3个节点，结果： 3
- 牛客网链接: 链表中倒数第k个结点
题解：
可以先算出链表的长度，链表总长度减去k，得到的就是倒数第k个节点，这种比较简单
第二种方法：
创建二个变量A和B
A先走k步，然后A和B同时走，当 A == null 时，B就是倒数第k个节点
源题代码：
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
// 判断是否为空链表
if(k <= 0 || head == null){
return null;
}
ListNode fast = head;
ListNode slow = head;
// fast 先走 k-1 步，或者可以先 k 步，不过最后判断条件要改成 fast != null
while(k-1 != 0){
fast = fast.next;
if(fast == null){
return null;
}
k--;
}
// fast 和 slow 同时前进
while(fast.next != null){
fast = fast.next;
slow = slow.next;
}
// 返回倒数第k个节点
return slow;
}
}
合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
- 力扣链接: 合并两个有序链表
题解：
定义一个头节点，通过对比数值大小，修改链表的指向，放到新的头节点的后面
源题代码：
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 创建新的链表头节点，头节的数据不重要，不会使用
ListNode newHead = new ListNode(1);
// 用 tmp 来修改节点的指向
ListNode tmp = newHead;
while(list1 != null && list2 != null){
if(list1.val < list2.val){
tmp.next = list1;
list1 = list1.next;
}else{
tmp.next = list2;
list2 = list2.next;
}
tmp = tmp.next;
}
if(list1 != null){
tmp.next = list1;
}
if(list2 != null){
tmp.next = list2;
}
// 返回的是新的节点
return newHead.next;
}
}
链表分割
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前
且不能改变原来的数据顺序，返回重新排列后的链表的头指针
- 牛客链接: 链表分割
题解：
以上题目可以根据链表节点的大小值分别定义二个变量来记录头节点和末尾节点，通过判断其大小值分别放到各自的链表节点中，最后合并起来
源题代码：
public class Partition {
public ListNode partition(ListNode pHead, int x) {
// write code here
ListNode as = null;
ListNode ae = null;
ListNode bs = null;
ListNode be = null;
ListNode cur = pHead;
if(pHead == null){
return null;
}
// 遍历链表
while(cur != null){
if(cur.val < x){
// 第一次插入节点时，给 小于x 初始化
if(as == null){
as = cur;
ae = cur;
}else{
// 不是第一次插入节点时
ae.next = cur;
ae = ae.next;
}
}else{
// 第一次插入节点时，给 大于等于x 的二个变量初始化
if(bs == null){
bs = cur;
be = cur;
}else{
be.next = cur;
be = be.next;
}
}
// cur 节点往后走
cur = cur.next;
}
// 假设链表里没有 小于x 的值时，直接返回 bs(大于x) 的链表
if(as == null){
return bs;
}
// 如果链表里没有大于等于x 的值时，直接返回 as(小于) 的链表
if(bs == null){
return as;
}
// 合并链表
ae.next = bs;
// 如果最后一个元素的地址不是 null 时，手动置 null
if(be.next != null){
be.next = null;
}
return as;
}
}
链表的回文结构
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900
示例：
链表：1 2 2 1
返回：true
题解：
先找到链表的中间节点，之后翻转中间节点后面的链表
然后一个从头开始，一个从末尾开始比较
源题代码：
public class PalindromeList {
public boolean chkPalindrome(ListNode head) {
// write code here
// 判断是否为空链表
if(head == null){
return false;
}
// 考虑只有一个节点的情况
if(head.next == null){
return true;
}
// 找中间节点
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
// 开始进行反转链表
ListNode cur = slow.next;
while(cur != null){
ListNode curNext = cur.next;
cur.next = slow;
slow = cur;
cur = curNext;
}
// 判断是否为回文数
while(head != slow){
if(head.val != slow.val){
return false;
}
// 偶数情况下
if(head.next == slow){
return true;
}
head = head.next;
slow = slow.next;
}
return true;
}
}
相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
如果两个链表不存在相交节点，返回 null
- 力扣链接: 相交链表
题解：
可以先计算二个链表的长度，再计算二个链表最长和最短之间的差值，然后让最长的链表先走 计算出的差值步 ，之后再同时走，最后比较
源题代码：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// 计算二个链表的长度
ListNode p1 = headA;// 指向最长的链表
ListNode p2 = headB;// 指向最短的链表
int a = fun(headA);
int b = fun(headB);
//计算最长的链表和最短的链表的差值
int n = a - b;
if(n < 0){
p1 = headB;
p2 = headA;
n = b - a;
}
//让最长的先走 如果A本来是最长的链表，那么就不用在上面替换
while(n-- != 0){
p1 = p1.next;
}
// 在相同的位置下进行比较
while(p1 != p2){
p1 = p1.next;
p2 = p2.next;
}
// 如果p1 == null
if(p1 == null){
return null;
}
return p1;
}
public int fun(ListNode head){
int count = 0;
while(head != null){
count++;
head = head.next;
}
return count;
}
}
环形链表
给你一个链表的头节点 head ，判断链表中是否有环
题解：
只需要判断最后一个元素是否为空，如果为 null 说明没有环
在有环的情况下，定义二个变量，速度不一样去跑，如果后面相遇了，说明有环
源题代码：
public class Solution {
public boolean hasCycle(ListNode head) {
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;
}
}
以上题在进行扩展，如果在有环的情况下，如何找到环的入口点？
- 力扣链接: 环形链表 II
题解：
-
源题代码：
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(fast == slow){
ListNode x = head;
while(x != slow){
x = x.next;
slow = slow.next;
}
return x;
}
}
return null;
}
}