每日一题之《剑指offer》14,15,16题
第十四题：链表中倒数第k 个节点
难易度：⭐
题目描述：
现有节点类：
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
输入一个链表，输出该链表中倒数第k个结点。
一般的思路是：从头节点开始遍历链表，记录链表的长度 n ，然后再次从头开始遍历，遍历到第n-k+1个节点处，返回即可，不过要注意的是需要判断几种case:如果链表为空时直接返回空即可，如果k > 链表的长度 n 或者 k <= 0 时，返回空,代码如下：
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null || k <= 0){
return null;
}
ListNode cur = head;
int listLen = 0;
while(cur != null){
cur = cur.next;
listLen++;
}
if(k > listLen){
return null;
}
for(int i = 1;i <= listLen - k;i++){
head = head.next;
}
return head;
}
}
这样做，很显然是可以的，但是能不能仅仅遍历一次链表就可以得到链表中倒数第k个节点呢？
思路：
准备一个指针 behind，等到cur指针遍历到链表的正数第k个位置时，behind 指针再从0位置出发，等到cur指针走完，behind会正好停在整个链表的倒数第k个位置。需要注意的是，我们也要判断各种case,如果k 的值要比 整个链表的长度还大，如何处理，这些细节是本题的关键。
代码如下：
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null || k <= 0){
return null;
}
ListNode cur = head;
ListNode behind = head;
for(int i = 0;i < k;i++){
if(cur != null){
cur = cur.next;
}else{
return null;
}
}
while(cur != null){
cur = cur.next;
behind = behind.next;
}
return behind;
}
}
第十五题：反转链表
难易度：⭐
题目描述：
给定链表的节点类
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
输入一个链表，反转链表后，输出新链表的表头。
本题是最简单的链表类问题了，应该熟练到可以白板coding秒写的程度，此处也就不再画图演示这个过程了，通过代码也可以知道整个过程是怎么发生的。其他的方法肯定没有经典代码优秀，不建议使用，还是老老实实遵循这种经典教科书的写法。
代码如下：
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head == null){
return null;
}
ListNode pre = null;
ListNode next = null;
while(head != null){
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
}
第十六题：合并两个排序的链表
难易度：⭐⭐
题目描述
有链表的节点类
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
输入两个单调递增的链表，输出两个链表合成后的链表;
当然我们需要合成后的链表满足单调不减规则。
本题是链表的归并排序，我们都熟知数组的排序。链表同数组是一样的，都是线性数据结构，数组可以的排序，在链表上自然也行得通。如果不熟悉归并排序的朋友，可以参考下我的文章，理解下归并排序
时间复杂度的认识,递归,归并排序
归并排序非常重要，如果你知道数组怎么样排序，链表其实也是一样的，此处就不解释说明merge的过程了
代码如下：
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1 == null && list2 == null){
return null;
}
if(list1 == null){
return list2;
}
if(list2 == null){
return list1;
}
ListNode dummyHead = new ListNode(-1);
ListNode cur = dummyHead;
while(list1 != null && list2 != null){
if(list1.val < list2.val){
cur.next = list1;
list1 = list1.next;
cur = cur.next;
}else{
cur.next = list2;
list2 = list2.next;
cur = cur.next;
}
}
if(list1 != null){
cur.next = list1;
}
if(list2 != null){
cur.next = list2;
}
return dummyHead.next;
}
}
本题中，我使用了dummyHead,作为新的链表头结点的头结点，这样做的原因是可以在merge的过程中，更简便地使用引用的指向，如果不使用dummyHead，那么一定程度上，你的代码会稍稍复杂那么一点点。使用了dummyHead后，最后结果返回dummyHead.next即可。除了归并写法，本题还可以使用经典的递归写法：
代码如下：
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1 == null && list2 == null){
return null;
}
if(list1 == null){
return list2;
}
if(list2 == null){
return list1;
}
if(list1.val < list2.val){
list1.next = Merge(list1.next,list2);
return list1;
}else{
list2.next = Merge(list2.next,list1);
return list2;
}
}
}
递归的解决方法，更是简单明了。
查看10道真题和解析