目录
链表一（基本概念和应用场景）+ 链表常见算法题-CSDN博客
ListNode代码
import java.util.Arrays;
public class ListNode {
int val;
ListNode next = null;
public ListNode(int val) {
this.val = val;
}
//遍历链表转换为字符串便于打印
public String Traversal(ListNode listNode) {
int[] arr = new int[getLength(listNode)];
int i = 0 ;
while (listNode != null){
arr[i] = listNode.val;
listNode = listNode.next;
i++;
}
return Arrays.toString(arr);
}
// 获取长度
public int getLength(ListNode head) {
int length = 0;
while (head != null) {
length++;
head = head.next;
}
return length;
}
}
链表中倒数最后k个结点
描述
输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。
如果该链表长度小于k，请返回一个长度为 0 的链表。
数据范围：0≤n≤105，0≤ai≤109，90≤k≤109
要求：空间复杂度 O(n)，时间复杂度O(n)
进阶：空间复杂度 O(1)，时间复杂度 O(n)
例如输入{1,2,3,4,5},2时，对应的链表结构如下图所示：
其中蓝色部分为该链表的最后2个结点，所以返回倒数第2个结点（也即结点值为4的结点）即可，系统会打印后面所有的节点来比较。
示例1
输入：{1,2,3,4,5},2
返回值：{4,5}
说明：返回倒数第2个节点4，系统会打印后面所有的节点来比较。
示例2
输入：{2},8
返回值：{}
解题思路
- 先算出链表的长度
- 算出到倒数第k个节点需要多少步
- 将指针移动指定步数，到达指定的节点。返回当前结点。
AC代码
不借助指针
public ListNode FindKthToTail (ListNode pHead, int k) {
// write code here
// 求出链表的长度
int length = getLength(pHead);
if(length < k){
return null;
}
// 算出链表要走多少步
int step = length - k;
// // 定义一个指针
// ListNode cur = pHead;
// 移动相应步数找到需要返回的节点
while(step != 0){
pHead = pHead.next;
step--;
}
return pHead;
}
//
public int getLength(ListNode head){
int length = 0;
while(head != null){
length++;
head = head.next;
}
return length;
}快慢指针
public ListNode FindKthToTailByTwoPointer(ListNode pHead, int k){
// 定义两个快慢指针
ListNode fast = pHead;
ListNode slow = pHead;
// fast 先走k步
while(k != 0){
if (fast != null){
// fast 往后走
fast = fast.next;
k--;
}else {
// 如果fast还没走到第k个位置 就是k大于链表长度，返回null
return null;
}
}
// 因为fast 先走k步，在保证两个指针一起走 他们的距离始终为k，
// 当fast到链尾的时候 slow所在的位置就是倒数第k个节点
while (fast != null){
fast = fast.next;
slow = slow.next;
}
//
return slow;
}删除链表中重复的结点
描述
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5
数据范围：链表长度满足 0≤n≤1000 ，链表中的值满足 1≤val≤1000
进阶：空间复杂度 O(n) ，时间复杂度 O(n)
例如输入{1,2,3,3,4,4,5}时，对应的输出为{1,2,5}，对应的输入输出链表如下图所示：
示例1
输入：{1,2,3,3,4,4,5}
返回值：{1,2,5}
示例2
输入：{1,1,1,8}
返回值：{8}
解题思路
- 使用两个工作指针 一个前赴(pre)指针在前，负责构建新的建表，一个当前(cur)指针去找重复节点的值，便于pre去连接。
- 总的来说就是去遍历链表，去寻找链表中重复出现的值，然后跳过这些值,使用pre去连接下一个节点值。
- 具体步骤如下代码：
AC代码
public class Solution {
public ListNode deleteDuplication(ListNode pHead) {
// 定义一个新的头节点 构建删除重复节点后的链表
ListNode nHead = new ListNode(0);
// 前赴指针
ListNode pre = nHead;
// 当前结点
ListNode cur = pHead;
// 将新的表头与pHead相连
nHead.next = pHead;
// 循环条件 要么当前节点为空 需要跳出循环 或者 工作指针到链尾需要跳出循环
while(cur != null && cur.next != null){
// 如果当前节点的值和下一个节点的值相等
if(cur.next !=null && cur.val == cur.next.val ){
// 持续找到连续重复的值一直移动指针 直到相邻两个节点的值不相等
while(cur != null && cur.next != null && cur.val == cur.next.val ){
// 后移指针
cur = cur.next;
}
// 移动到下一个暂时没有重复的节点值的位置
cur = cur.next;
// 将pre连接到重复节点的最后一个节点的后一个节点
// 这个操作相当于删除当前的有重复值的连续节点 直接连接到下一个暂时不是重复的节点位置
pre.next = cur;
}else{
// pre跟着cur一起移动
pre = cur;
cur = cur.next;
}
}
return nHead.next;
}
}可测试运行代码(需要ListNode代码，在文章开头)：
public static void main(String[] args) {
ListNode node = new ListNode(1);
node.next = new ListNode(3);
node.next.next = new ListNode(3);
node.next.next.next = new ListNode(5);
node.next.next.next.next = new ListNode(4);
String before = node.Traversal(node);
System.out.println("删除重复节点后的值为： " + before);
ListNode listNode = deleteDuplication(node);
String end = listNode.Traversal(listNode);
System.out.println("删除重复节点后的值为： " + end);
}
public static ListNode deleteDuplication(ListNode pHead) {
// 定义一个新的头节点 构建删除重复节点后的链表
ListNode nHead = new ListNode(0);
// 前赴指针
ListNode pre = nHead;
// 当前结点
ListNode cur = pHead;
// 将新的表头与pHead相连
nHead.next = pHead;
// 循环条件 要么当前节点为空 需要跳出循环 或者 工作指针到链尾需要跳出循环
while(cur != null && cur.next != null){
// 如果当前节点的值和下一个节点的值相等
if(cur.val == cur.next.val ){
// 持续找到连续重复的值一直移动指针 直到相邻两个节点的值不相等
while(cur.next != null && cur.val == cur.next.val ){
// 后移指针
cur = cur.next;
}
// 移动到下一个暂时没有重复的节点值的位置
cur = cur.next;
// 将pre连接到重复节点的最后一个节点的后一个节点
// 这个操作相当于删除当前的有重复值的连续节点 直接连接到下一个暂时不是重复的节点位置
pre.next = cur;
}else{
// pre跟着cur一起移动
pre = cur;
cur = cur.next;
}
}
return nHead.next;
}运行结果
图解
