⭐1.反转链表
题目：
解题思路：
如下图，我们要实现的就是这样一个效果
要实现上图的效果，需要以下步骤：
①设置两个指针，cur 指向链表头节点，prev 指向空
②暂存 cur 的后继节点，curNext = cur.next
③将 cur.next 反指向prev（一开始prev为空）
④prev 指针后移，即将 prev 指向 cur
⑤cur 指针后移 ，即将 cur 指向 2 中暂存的 curNext 节点
⑥循环： 第2 到 5 步，直到 cur 遍历完整个链表
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { if(head==null){ System.out.println("链表为空"); } //设置两个指针，cur 指向链表头节点，prev 指向空 ListNode prev = null; ListNode cur = head; while(cur != null){ ListNode curNext = cur.next;//暂存 cur 的后继节点，curNext = cur.next cur.next =prev;//将 cur.next 反指向prev（一开始prev为空） prev = cur;//prev 指针后移，即将 prev 指向 cur cur = curNext;//cur 指针后移 ，即将 cur 指向 2 中暂存的 curNext 节点 }//循环： 第2 到 5 步，直到 cur 遍历完整个链表 return prev; } }
⭐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 middleNode(ListNode head) { ListNode fast = head;//快指针一开始指向头结点 ListNode slow = head;//慢指针一开始也指向头结点 while(fast!=null&&fast.next!=null){//由于要考虑偶数链表返回中间靠后的节点 //所以要多设置一个fast.next!=null条件 fast=fast.next.next;//快指针往后走两步 slow=slow.next;//慢指针往后走一步 } return slow;//返回慢指针 } }
⭐3.输入一个链表输出该链表中倒数第K个节点
题目：
解题思路：
这题和上题一样，采用双指针的办法，遍历链表一次就能达到目的
具体需要以下步骤：
①初始化： 前指针 former 、后指针 latter ，双指针都指向头节点 head 。
②构建双指针距离： 前指针 former 先向前走 k-1 步（结束后，双指针 former 和 latter 间相距 k-1步）。
③双指针共同移动： 循环中，双指针 former 和 latter 每轮都向前走一步，直至 former 走到链表 尾节点 时跳出（跳出后， latter 与尾节点距离为 k-1步，即 latter 指向倒数第 k 个节点）
④返回值： 返回 latter 即可。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode getKthFromEnd(ListNode head, int k) { ListNode former = head;//设置一个先行节点，一开始指向头结点 ListNode latter = head;//再设置一个后行节点，一开始指向头结点 for(int i=1; i < k; i++){//构建双节点之间距离 former = former.next;// } //构建距离完成之后，双节点同时向后走，直至先行节点到达尾节点处 while(former.next!=null){// former = former.next;// latter = latter.next;// } return latter;//此时latter距离尾节点k-1步，也就是指向倒数第k个节点，直接返回latter即可 } }
⭐4.将两个有序链表合并为一个新的有序链表并返回
题目：
解题思路：
具体步骤如下
①设置傀儡节点，傀儡节点后边的节点组成的链表就是合并后的链表
②比较两个链表的每个节点，存入傀儡节点后的合并链表
③当有一条链已经遍历完成则将另一条链接到合并链表的尾部
④最后返回的是傀儡节点的下一个节点，这才是合并后的链表的头结点
/** * 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 mergeTwoLists(ListNode l1, ListNode l2) { ListNode newhead = new ListNode(-1);//创建一个虚拟傀儡节点，最后返回的是.next ListNode tmp =newhead;//创建局部引用，指向傀儡节点 while (l1!=null && l2!=null) {//依次比较节点 if (l1.val < l2.val) {//情况1 tmp.next = l1;//将节点存入合并链表 l1 = l1.next;//L2往后走一步 tmp = tmp.next;//合并链表也要往后走一步好用于储存下一个比较结果 } else { //情况2 tmp.next = l2;//将节点存入合并链表 l2 = l2.next;//L2往后走一步 tmp = tmp.next;//合并链表也要往后走一步好用于储存下一个比较结果 } } if (l1==null){//当第一条链先走完 tmp.next = l2;//将第二条链接到合并链表后 } if (l2==null){//当第二条链先走完 tmp.next = l1;//将第一条链接到合并链表后 } return newhead.next;//最终返回傀儡节点的下一个节点，也就是合并链表的头结点 }
