🤞目录🤞
💖1. 链表中倒数第k个结点
💖2. 反转链表（五种解题思路）
💖3. 合并两个排序的链表
【大家好，我是爱干饭的猿，如果喜欢这篇文章，点个赞👍，关注一下吧，后续会一直分享题目与算法思路】
🥝1. 链表中倒数第k个结点
描述
输入一个链表，输出该链表中倒数第k个结点。
解题思路：
🎈1. 方法一：我们可以先遍历链表，得到节点总个数n，然后return 第（n - k）个节点即可。
🎈2. 方法二：我们可以用前后指针法，前后指针都先指向头结点，然后让前指针先走k步，继而让前后指针都往后走，直到前指针节点为空时，后指针节点刚好走到了倒数第k个节点位置。
💡 方法一：代码如下：
// 遍历数组
public ListNode FindKthToTail1(ListNode head,int k) {
if(head == null){
return null;
}
// 记录节点总数
int count = 0;
for(ListNode x = head ; x != null;x = x.next){
count ++;
}
// 如果节点总数小于k ，说明不存在该节点
if(count < k){
return null;
}
// 找到倒数第k 个节点，（找到第（n-k）个节点）
for(int i = 0;i < count - k;i ++){
head = head.next;
}
return head;
}💡方法二：代码如下：
// 前后指针法
public ListNode FindKthToTail2(ListNode head,int k) {
if(head == null){
return null;
}
// 前后指针
ListNode first = head;
ListNode second = head;
// 先让前指针走k 步
while(k > 0 && first != null){
first = first.next;
k--;
}
// 然后前后指针一起向后走，当前指针走到末尾，后指针刚好走到倒数第 k的位置
while(first != null){
first = first.next;
second = second.next;
}
// 程序走到这一步
// 如果k>0，说明k大于节点总数，不存在该节点
return k > 0 ? null : second;
}🥝2. 反转链表（五种解题思路）
描述
给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
数据范围：10000 ≤n ≤ 1000
要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。
例：如当输入链表{1,2,3}时，经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
以上转换过程如下图所示：
解题思路：
🎈1. 方法一：头插（带虚拟头结点），先设置一个虚拟头节点dummyNode，然后将每一个节点都插入在虚拟头节点之后完成头插，只需返回dummyNode.next即可。
🎈2. 方法二：头插（不带虚拟头结点），先设置一个空节点newNode，将第一个节点（head）头插在newNode节点之前，更新newNode节点为该节点，并更新head节点（head = head.next），不断循环此过程，当head == null 时，退出循环，返回newNode节点即可。
🎈3. 方法三：原地移动（双指针法），和方法二基本一致，只是多了个指针指向head。
🎈4. 方法四：原地移动（三指针法），定义三个指针 left , mid , right 分别指向链表前三个元素，我们只需要使 mid.next = left，然后三个指针都向后走一步，循环进行就能使链表反转。
🎈5. 方法五：递归，思考，反转时我们只需要将第二个节点的next指向 指向前一个节点即可。
💡方法一：代码如下：
// 头插1（new 新节点）
public ListNode ReverseList1(ListNode head) {
if(head==null|| head.next==null){
return head;
}
ListNode dummyHead = new ListNode(-1);
while(head != null){
// 创建一个节点存当前head的值
ListNode cur = new ListNode(head.val);
// 头插
cur.next = dummyHead.next;
dummyHead.next = cur;
head = head.next;
}
return dummyHead.next;
}💡方法二：代码如下：
// 头插2（不用new 空间复杂度O1）
public ListNode ReverseList1_2(ListNode head) {
if(head==null|| head.next==null){
return head;
}
ListNode newNode = null;
while(head != null){
ListNode pre = head;
head = head.next;
//再将p标识的节点头查到新链表
pre.next = newNode;
newNode = pre;
}
return newNode;
}💡方法三：代码如下：
// 原地移动（双指针）和 头插2类似
public ListNode ReverseList2(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode prev = null;
// 当前需要处理的节点(需要反转)
ListNode cur = head;
while (cur != null){
// 存储cur之后的链
ListNode node = cur.next;
// 原地移动，（改变next指向）
cur.next = prev;
prev = cur;
cur = node;
}
return prev;
}💡方法四：代码如下：
// 原地移动（三指针）
public ListNode ReverseList3(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode left = head;
ListNode mid = left.next;
ListNode right = mid.next;
// 反转中间节点，但是当right 为 null时，最后一个节点没有处理
while (right != null){
mid.next = left;
left = mid;
mid = right;
right = right.next;
}
// 处理最后一个节点 || 当链表只有两个节点时
mid.next = left;
head.next = null;
return mid;
}💡方法五：代码如下：
// 递归写法
public ListNode ReverseList4(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode second = head.next;
// 反转第二个节点之后的子链表
ListNode newHead = ReverseList4(head.next);
// 反转链表（每次递归都只是处理second节点前后指向）
second.next = head;
head.next = null;
return newHead;
}🥝3. 合并两个排序的链表
描述
输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围：10000 ≤ n ≤1000，节点值 −1000 ≤ 节点值 ≤1000
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
例：如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：
解题思路：
🎈1. 方法一：先定义一个虚拟头节点dummyNode，然后比较两条链头结点的大小，将较小的头结点放在虚拟头节点之后，并将该链的头结点后移一位，（list = list.next），返回dummyNode.next即可。
🎈2. 方法二：递归，如果list1.val < list2.val，list1头结点之后就接list2，反之，list2头结点就接list1。
💡方法一：代码如下：
// 方法一
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1 == null){
return list2;
}
if(list2 == null){
return list1;
}
ListNode dummyNode = new ListNode(-1);
// 定义一个last节点，指向新链表的末节点位置
ListNode last = dummyNode;
while(list1 != null && list2 != null){
if(list1.val < list2.val){
// 将list1节点 接在last 后
last.next = list1;
// 更新末尾节点位置
last = list1;
// 头结点后移一位
list1 = list1.next;
}else {
// 将list2节点 接在last 后
last.next =list2;
// 更新末尾节点位置
last = list2;
// 头结点后移一位
list2 = list2.next;
}
}
if(list1 == null){
//如果list1 空了，直接接list2链
last.next = list2;
}
if(list2 == null){
//如果list2 空了，直接接list1链
last.next = list1;
}
return dummyNode.next;
}💡方法二：代码如下：
// 递归
public ListNode Merge2(ListNode list1,ListNode list2) {
if(list1 == null){
return list2;
}
if(list2 == null){
return list1;
}
if(list1.val < list2.val){
list1.next = Merge2(list1.next,list2);
// 如果list1.val < list2.val，list2头结点之后就接list1
return list1;
}else {
list2.next = Merge2(list1,list2.next);
// 反之，list1头结点就接list2
return list2;
}
}相关文章
