题目描述
思路一：采用两次遍历
- 第一遍遍历先获取链表的长度length
- 第二次从dummy节点开始走length - n步
- 然后将该节点指向下下个节点
思路二：采用一次遍历
- 设置虚拟节点dummyHead指向head
- 设定双指针p和q，初始都指向虚拟节点dummyHead
- 移动q，直到p与q之间相隔的元素个数为n(即q走n+1步)
- 同时移动p与q，直到q指向的为NULL
- 将p的下一个节点指向下下个节点
方法一：对应思路一
/**
* 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 removeNthFromEnd(ListNode head, int n) {
ListNode p = head;
ListNode dummy = new ListNode(0, head);
ListNode q = dummy;
int length = 0;
// p就是用来统计链表的长度
while (p != null) {
length ++;
p = p.next;
}
// q是用来找到待删除节点的前一个节点
// 然后将该节点的next指针指向下下个元素
for (int i = 0; i < length - n; i ++) {
q = q.next;
}
q.next = q.next.next;
return dummy.next;
}
}
方法二：对应思路二
/**
* 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 removeNthFromEnd(ListNode head, int n) {
// 设置虚拟节点dummyHead指向head
ListNode dummy = new ListNode(0, head);
// 设定双指针p和q，初始都指向虚拟节点dummyHead
ListNode p = dummy, q = dummy;
// 移动q，直到p与q之间相隔的元素个数为n
for (int i = 0; i < n + 1; i ++) {
q = q.next;
}
// 同时移动p与q，直到q指向的为NULL
while (q != null) {
p = p.next;
q = q.next;
}
// 将p的下一个节点指向下下个节点
p.next = p.next.next;
return dummy.next;
}
}