1,双指针求解
这题要求链表的倒数第k个节点,最简单的方式就是使用两个指针,第一个指针先移动k步,然后第二个指针再从头开始,这个时候这两个指针同时移动,当第一个指针到链表的末尾的时候,返回第二个指针即可。注意,如果第一个指针还没走k步的时候链表就为空了,我们直接返回null
即可。
public ListNode FindKthToTail(ListNode pHead, int k) { if (pHead == null) return pHead; ListNode first = pHead; ListNode second = pHead; //第一个指针先走k步 while (k-- > 0) { if (first == null) return null; first = first.next; } //然后两个指针在同时前进 while (first != null) { first = first.next; second = second.next; } return second; }
2,使用栈解决
这题要求的是返回后面的k个节点,我们只要把原链表的结点全部压栈,然后再把栈中最上面的k个节点出栈,出栈的结点重新串成一个新的链表即可,原理也比较简单,直接看下代码。
public ListNode FindKthToTail(ListNode pHead, int k) { Stack<ListNode> stack = new Stack<>(); //链表节点压栈 int count = 0; while (pHead != null) { stack.push(pHead); pHead = pHead.next; count++; } if (count < k || k == 0) return null; //在出栈串成新的链表 ListNode firstNode = stack.pop(); while (--k > 0) { ListNode temp = stack.pop(); temp.next = firstNode; firstNode = temp; } return firstNode; }
3,递归求解
之前讲过链表的逆序打印410,剑指 Offer-从尾到头打印链表,其中有这样一段代码
public void reversePrint(ListNode head) { if (head == null) return; reversePrint(head.next); System.out.println(head.val); }
这段代码其实很简单,我们要理解他就要弄懂递归的原理,递归分为两个过程,递和归,看一下下面的图就知道了,先往下传递,当遇到终止条件的时候开始往回走。
前面也刚讲过递归的原理426,什么是递归,通过这篇文章,让你彻底搞懂递归,这题如果使用递归的话,我们先来看一下递归的模板
public ListNode getKthFromEnd(ListNode head, int k) { //终止条件 if (head == null) return head; //递归调用 ListNode node = getKthFromEnd(head.next, k); //逻辑处理 …… }
终止条件很明显就是当节点head为空的时候,就没法递归了,这里主要看的是逻辑处理部分,当递归往下传递到最底端的时候,就会触底反弹往回走,在往回走的过程中记录下走过的节点,当达到k的时候,说明到达的那个节点就是倒数第k个节点,直接返回即可,如果没有达到k,就返回空,搞懂了上面的过程,代码就很容易写了
//全局变量,记录递归往回走的时候访问的结点数量 int size; public ListNode FindKthToTail(ListNode pHead, int k) { //边界条件判断 if (pHead == null) return pHead; ListNode node = FindKthToTail(pHead.next, k); ++size; //从后面数结点数小于k,返回空 if (size < k) { return null; } else if (size == k) { //从后面数访问结点等于k,直接返回传递的结点k即可 return pHead; } else { //从后面数访问的结点大于k,说明我们已经找到了, //直接返回node即可 return node; } }
上面代码在仔细一看,当size小于k的时候node节点就是空,所以我们可以把size大于k和小于k合并为一个,这样代码会更简洁一些
int size; public ListNode FindKthToTail(ListNode pHead, int k) { if (pHead == null) return pHead; ListNode node = FindKthToTail(pHead.next, k); if (++size == k) return pHead; return node; }
我把部分算法题整理成了PDF文档,截止目前总共有900多页,大家可以下载阅读
链接:https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666