一、链表的算法题（目前10道）
1. 移除链表元素（力扣；思路：前后指针）
题目：给你一个链表的头节点 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 prev = head; ListNode cur = head.next; while(cur != null){ if(cur.val == val){ prev.next = cur.next; cur = cur.next; }else{ cur = cur.next; prev = prev.next; } } //最后处理第一个节点 if(head.val == val){ head = head.next; } return head; } }
运行结果：
时间复杂度和空间复杂度：
（1）时间复杂度：O(N)；（2）空间复杂度：O(1)
2. 反转一个单链表 （力扣；思路：头插法）
题目：给你单链表的头节点 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 reverseList(ListNode head) { //特殊情况一：如果链表为空，就不需要返回 if(head == null){ return null; } //特殊情况二：只有一个节点 if(head.next == null){ return head; } ListNode cur = head.next;//把第二个节点地址保存起来 head.next = null;//到时第一个节点的next肯定为空，在这里就可以提前改了 //进入循环，开始进行头插法 while(cur != null){ ListNode curNext = cur.next;//保存cur指向的节点 cur.next = head;//将第一个节点的地址赋值给cur.next head = cur; cur = curNext; } return head; } }
运行结果：
时间复杂度和空间复杂度：
（1）时间复杂度：O(N)；空间复杂度：O(1)
3. 链表的中间结点（力扣；思路：快慢指针）
题目：思路给定一个带有头结点 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 middleNode(ListNode head) { //特殊情况：如果只有一个结点 if(head.next == null){ return head; } ListNode quick = head;//快指针 ListNode slow = head;//慢指针 //有两种条件都成立表示快指针不走了，（1）quick为空 （2）quick.next为空 while(quick != null && quick.next != null){ quick = quick.next.next; slow = slow.next; } return slow; } }
运行结果：
时间复杂度和空间复杂度：
（1）时间复杂度：O(N)；（2）空间复杂度：O(1)
4. 链表中倒数第k个结点（牛客网；思路：①快慢指针、②倒数第几个与步数的关系）
题目：输入一个链表，输出该链表中倒数第k个结点。
思路：
代码：
思路一：
import java.util.*; /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Solution { public ListNode FindKthToTail(ListNode head, int k) { //输入值是否正确的判断 if(k <= 0 || head == null){ return null; } ListNode quick = head; ListNode slow = head; //先让quick走k - 1步 while (k - 1 != 0){ quick = quick.next; if(quick == null){ return null; } k--; } //快慢指针一起走 while(quick.next != null){ quick = quick.next; slow = slow.next; } return slow; } }
思路二：
public ListNode findKthToTail2(int k) { //输入值是否正确的判断 if(k <= 0 || head == null){ return null; } int count = 0; ListNode cur = head; while(cur != null){ count++; cur = cur.next; } int i = count - k; cur = head; if(i < 0){ return null; } while(i > 0){ cur = cur.next; i--; } return cur; }
运行结果：
时间复杂度和空间复杂度：
（1）时间复杂度：O(N)；（2）空间复杂度：O(1)
5. 合并两个有序链表（力扣）
题目：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路：
代码：
//合并两个升序链表，有问题 public ListNode mergeTwoLists(ListNode list1, ListNode list2){ //处理空表的情况 if(list1 == null && list2 !=null){ return list2; }else if(list1 != null && list2 == null){ return list1; }else if(list1 == null&&list2 == null){ return null; } //创建两个地址引用，指向两个链表的首元素结点 ListNode cur1 = list1; ListNode cur2 = list2; ListNode cur3 = null;//始终指向新链表的终端结点 //创建一个newList引用 ListNode newList = null; if (cur1.val <= cur2.val){ newList = cur1; cur1 = cur1.next; cur3 = newList; }else if(cur1.val >= cur2.val){ newList = cur2; cur2 = cur2.next; cur3 = newList; } //开始比较 while(cur1 != null && cur2 != null ){ if(cur1.val <= cur2.val){ cur3.next = cur1; cur3 = cur3.next; cur1 = cur1.next; }else if(cur1.val > cur2.val){ cur3.next = cur2; cur3 = cur3.next; cur2 = cur2.next; } } //当cur1 == null或cur2 == null时，意味着已经到链表的结尾，此时还需要将没有连接上的链表（cur1或cur2）连接接上 cur3.next = null; if(cur1 != null){ cur3.next = cur1; } if(cur2 != null){ cur3.next = cur2; } return newList; }
运行结果：
6. 链表分割（牛客网）
题目：现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
思路：
代码：
/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/ public class Partition { public ListNode partition(ListNode pHead, int x) { // write code here //把整个链表看成两部分，创建四个引用来分别指向这两部分 ListNode bs = null;//小于x部分的起始引用 ListNode be = null;//小于x部分的终端引用 ListNode as = null;//大于或等于x部分的起始引用 ListNode ae = null;//大于或等于x部分的终端引用 ListNode cur = pHead; //开始循环 while(cur != null){ //有两种可能性，小于x或者大于等于x if(cur.val < x){ //这部分也有两种情况，①当bs和be都为空，②bs不会空 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; } //有可能不会同时存在小于x和大于等于x的数据 if(bs == null){ return as; } //特殊情况：如果第一段不为空 be.next = as; //如果第二段为空 if(as != null){ ae.next = null; } return bs; } }
运行结果：
7. 相交链表（力扣）
题目：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
思路：
代码：
public MySinglelist.ListNode getIntersectionNode(MySinglelist.ListNode headA, MySinglelist.ListNode headB) { int lenA = 0;//用来记录长度 int lenB = 0; MySinglelist.ListNode pl = headA; MySinglelist.ListNode ps = headB; //计算pl和ps的链表长度 while(pl != null){ lenA++; pl = pl.next; } while (ps != null){ lenB++; ps = ps.next; } //1. len一定是一个正数 2.pl指向的链表一定是最长的 ps 指向的链表一定是最短的 pl = headA; ps = headB; //计算彼此之间的差值 int len = lenA - lenB; if(len < 0){ pl = headB; ps = headA; len = lenB - lenA; } //先让长度多的链表先走len步 while(len != 0){ pl = pl.next; len--; } //开始找相交的节点 while(pl != ps){ ps = ps.next; pl = pl.next; } //pl == ps /* if(pl == null) { return null; }*/ return pl; }
运行结果：
8. 链表的回文结构（牛客网）
题目：对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
思路：
定义快慢指针：
（1）找到中间结点
（2）翻转慢指针到快指针部分的结点
（3）首尾互相判断是否符合回文结构
代码：
public boolean chkPalindrome(ListNode head) { if(head == null){ return false; } if(head.next == null){ return true; } // write code here //先定义快慢指针 ListNode quick = head; ListNode slow = head; //1. 找中间结点 while(quick != null && quick.next != null){ quick = quick.next.next; slow = slow.next; } //2. 翻转 ListNode cur = slow.next; while(cur != null){ ListNode curNext = cur.next;//先记录下来后一个结点 cur.next = slow;//实现翻转 slow = cur;//保存上一个结点的地址 cur = curNext;//找到下一个结点 } //3.开始判断 cur = head; while(cur != slow){ //如果不是不相等，返回false if(cur.val != slow.val){ return false; } //判断偶数的情况： if(cur.next == slow){ return true; } cur = cur.next; slow = slow.next; } return true; }
运行结果：
9. 环形链表（力扣；思路：快慢指针、数学追击问题）
题目：给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
思路：
代码：
//判断链表是否有环 //第一种写法 public boolean hasCycle() { 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; } //第二种写法 public boolean hasCycle2() { 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 false; } return true; }
运行结果：
