如果K 值小于0，如何找到要删除节点的前一个节点呢？

如果K 值小于0，如何找到要删除节点的前一个节点呢？方法如下：

1．重新从头节点开始走，每移动一步，就让K 的值加1。

2．当K 等于0时，移动停止，移动到的节点就是要删除节点的前一个节点。

这样做是非常好理解的，因为如果链表长度为N ，要删除倒数第K 个节点，很明显，倒数第K 个节点的前一个节点就是第N -K 个节点。在第一次遍历后，K 的值变为K -N 。第二次遍历时，K 的值不断加1，加到0就停止遍历，第二次遍历当然会停到第N -K 个节点的位置。

具体过程请参看如下代码中的removeLastKthNode方法。

public class Node { public int value; public Node next; public Node(int data) { this.value = data; } } public Node removeLastKthNode(Node head, int lastKth) { if (head == null || lastKth < 1) { return head; } Node cur = head; while (cur ! = null) { lastKth--; cur = cur.next; } if (lastKth == 0) { head = head.next; } if (lastKth < 0) { cur = head; while (++lastKth ! = 0) { cur = cur.next; } cur.next = cur.next.next; } return head; }

对于双链表的调整，几乎与单链表的处理方式一样，注意last指针的重连即可。具体过程请参看如下代码中的removeLastKthNode方法。

public class DoubleNode { public int value; public DoubleNode last; public DoubleNode next; public DoubleNode(int data) { this.value = data; } } public DoubleNode removeLastKthNode(DoubleNode head, int lastKth) { if (head == null || lastKth < 1) { return head; } DoubleNode cur = head; while (cur ! = null) { lastKth--; cur = cur.next; } if (lastKth == 0) { head = head.next; head.last = null; } if (lastKth < 0) { cur = head; while (++lastKth ! = 0) { cur = cur.next; } DoubleNode newNext = cur.next.next; cur.next = newNext; if (newNext ! = null) { newNext.last = cur; } } return head; }

删除链表的中间节点和a/b处的节点

【题目】

给定链表的头节点head，实现删除链表的中间节点的函数。

例如：

不删除任何节点；

1->2，删除节点1；

1->2->3，删除节点2；

1->2->3->4，删除节点2；

1->2->3->4->5，删除节点3；

进阶：

给定链表的头节点head、整数a和b，实现删除位于a/b处节点的函数。

例如：

链表：1->2->3->4->5，假设a/b的值为r。

如果r等于0，不删除任何节点；

如果r在区间(0，1/5]上，删除节点1；

如果r在区间(1/5，2/5]上，删除节点2；

如果r在区间(2/5，3/5]上，删除节点3；

如果r在区间(3/5，4/5]上，删除节点4；

如果r在区间(4/5，1]上，删除节点5；

如果r大于1，不删除任何节点。

【难度】

士　★☆☆☆

【解答】

先来分析原问题，如果链表为空或者长度为1，不需要调整，则直接返回；如果链表的长度为2，将头节点删除即可；当链表长度到达3，应该删除第2个节点；当链表长度为4，应该删除第2个节点；当链表长度为5，应该删除第3个节点……也就是链表长度每增加2(3，5，7…)，要删除的节点就后移一个节点。删除节点的问题在之前的题目中我们已经讨论过，如果要删除一个节点，则需要找到待删除节点的前一个节点。

具体过程请参看如下代码中的removeMidNode方法。

public class Node { public int value; public Node next; public Node(int data) { this.value = data; } } public Node removeMidNode(Node head) { if (head == null || head.next == null) { return head; } if (head.next.next == null) { return head.next; } Node pre = head; Node cur = head.next.next; while (cur.next ! = null && cur.next.next ! = null) { pre = pre.next; cur = cur.next.next; } pre.next = pre.next.next; return head; }

接下来讨论进阶问题，首先需要解决的问题是，如何根据链表的长度n ，以及a与b的值决定该删除的节点是哪一个节点呢？根据如下方法：

先计算double r = ((double) (a * n)) / ((double) b)的值，然后r向上取整之后的整数值代表该删除的节点是第几个节点。

下面举几个例子来验证一下：

如果链表长度为7，a=5，b=7。

r = (7*5)/7 = 5.0，向上取整后为5，所以应该删除第5个节点。

如果链表长度为7，a=5，b=6。

r = (7*5)/6 = 5.8333…，向上取整后为6，所以应该删除第6个节点。

如果链表长度为7，a=1，b=6。

r = (7*1)/6 = 1.1666…，向上取整后为2，所以应该删除第2个节点。

知道该删除第几个节点之后，接下来找到需要删除节点的前一个节点即可。具体过程请参看如下代码中的removeByRatio方法。

public Node removeByRatio(Node head, int a, int b) { if (a < 1 || a > b) { return head; } int n = 0; Node cur = head; while (cur ! = null) { n++; cur = cur.next; } n = (int) Math.ceil(((double) (a * n)) / (double) b); if (n == 1) { head = head.next; } if (n > 1) { cur = head; while (--n ! = 1) { cur = cur.next; } cur.next = cur.next.next; } return head; }

反转单向和双向链表

【题目】

分别实现反转单向链表和反转双向链表的函数。

【要求】

如果链表长度为N ，时间复杂度要求为O (N )，额外空间复杂度要求为O (1)。

【难度】

士　★☆☆☆

【解答】

本题比较简单，读者做到代码一次成型，运行不出错即可。

反转单向链表的函数如下，函数返回反转之后链表新的头节点：

public class Node { public int value; public Node next; public Node(int data) { this.value = data; } } public Node reverseList(Node head) { Node pre = null; Node next = null; while (head ! = null) { next = head.next; head.next = pre; pre = head; head = next; } return pre; }

反转双向链表的函数如下，函数返回反转之后链表新的头节点：

public DoubleNode { public int value; public DoubleNode last; public DoubleNode next; public DoubleNode(int data) { this.value = data; } } public DoubleNode reverseList(DoubleNode head) { DoubleNode pre = null; DoubleNode next = null; while (head ! = null) { next = head.next; head.next = pre; head.last = next; pre = head; head = next; } return pre; }

反转部分单向链表

【题目】

给定一个单向链表的头节点head，以及两个整数from和to，在单向链表上把第from个节点到第to个节点这一部分进行反转。

例如：

1->2->3->4->5->null，from=2，to=4

调整结果为：1->4->3->2->5->null

再如：

1->2->3->null，from=1，to=3

调整结果为：3->2->1->null

【要求】

1．如果链表长度为N ，时间复杂度要求为O (N )，额外空间复杂度要求为O (1)。

2．如果不满足1<=from<=to<=N，则不用调整。

【难度】

士　★☆☆☆

【解答】

本题有可能存在换头的问题，比如题目的第二个例子，所以函数应该返回调整后的新头节点，整个处理过程如下：

1．先判断是否满足1<=from<=to<=N，如果不满足，则直接返回原来的头节点。

2．找到第from-1个节点fPre和第to+1个节点tPos。fPre即是要反转部分的前一个节点，tPos是反转部分的后一个节点。把反转的部分先反转，然后正确地连接fPre和tPos。

例如：1->2->3->4->null，假设fPre为节点1，tPos为节点4，要反转部分为2->3。先反转成3->2，然后fPre连向节点3，节点2连向tPos，就变成了1->3->2->4->null。

3．如果fPre为null，说明反转部分是包含头节点的，则返回新的头节点，也就是没反转之前反转部分的最后一个节点，也是反转之后反转部分的第一个节点；如果fPre不为null，则返回旧的头节点。