🤞目录🤞
【大家好，我是爱干饭的猿，如果喜欢这篇文章，点个赞👍，关注一下吧，后续会一直分享题目与算法思路】
🥝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; } }
