1,非递归解决
这题让删除链表的倒数第n个节点,首先最容易想到的就是先求出链表的长度length
,然后就可以找到要删除链表的前一个结点,让他的前一个结点指向要删除结点的下一个结点即可,这里就以示例为例画个图看一下
再来看下代码
public ListNode removeNthFromEnd(ListNode head, int n) { ListNode pre = head; int last = length(head) - n; //如果last等于0表示删除的是头结点 if (last == 0) return head.next; //这里首先要找到要删除链表的前一个结点 for (int i = 0; i < last - 1; i++) { pre = pre.next; } //然后让前一个结点的next指向要删除节点的next pre.next = pre.next.next; return head; } //求链表的长度 private int length(ListNode head) { int len = 0; while (head != null) { len++; head = head.next; } return len; }
2,双指针求解
上面是先计算链表的长度,其实不计算链表的长度也是可以,我们可以使用两个指针,一个指针fast
先走n
步,然后另一个指针slow
从头结点开始,找到要删除结点的前一个结点,这样就可以完成结点的删除了。
public ListNode removeNthFromEnd(ListNode head, int n) { ListNode fast = head; ListNode slow = head; //fast移n步, for (int i = 0; i < n; i++) { fast = fast.next; } //如果fast为空,表示删除的是头结点 if (fast == null) return head.next; while (fast.next != null) { fast = fast.next; slow = slow.next; } //这里最终slow不是倒数第n个节点,他是倒数第n+1个节点, //他的下一个结点是倒数第n个节点,所以删除的是他的下一个结点 slow.next = slow.next.next; return head; }
3,递归解决
我们知道获取链表的长度除了上面介绍的一种方式以外,还可以写成递归的方式,比如
//求链表的长度 private int length(ListNode head) { if (head == null) return 0; return length(head.next) + 1; }
上面计算链表长度的递归其实可以把它看做是从后往前计算,当计算的长度是n的时候就表示遍历到了倒数第n个节点了,这里只要求出倒数第n+1个节点,问题就迎刃而解了,来看下代码
public ListNode removeNthFromEnd(ListNode head, int n) { int pos = length(head, n); // 说明删除的是头节点 if (pos == n) return head.next; return head; } // 获取节点所在位置,逆序 public int length(ListNode node, int n) { if (node == null) return 0; int pos = length(node.next, n) + 1; //获取要删除链表的前一个结点,就可以完成链表的删除 if (pos == n + 1) node.next = node.next.next; return pos; }
我把部分算法题整理成了PDF文档,截止目前总共有900多页,大家可以下载阅读
链接:https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666