LeetCode19-删除链表的倒数第N个结点

LeetCode19-删除链表的倒数第N个结点

直接删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//计算链表长度法
public ListNode removeNthFromEnd(ListNode head, int n) {
//创建头结点
ListNode dummy = new ListNode(0, head);
//计算长度
//head 从0开始
int length = getLength(head);
//头结点从1开始
ListNode cur = dummy;
for (int i = 1; i <= length - n ; ++i) {
cur = cur.next;
}
cur.next = cur.next.next;
return dummy.next;
}

public int getLength(ListNode head) {
int length = 0;
while (head != null) {
head = head.next;
++length;
}
return length;
}

使用辅助栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//使用辅助栈
public ListNode removeNthFromEnd1(ListNode head, int n) {
//创建头结点
ListNode dummyHead = new ListNode();
dummyHead.next = head;
Stack<ListNode> stack = new Stack<>();
ListNode cur = dummyHead;
while (cur != null) {
stack.push(cur);
cur = cur.next;
}
for (int i = 1; i <= n; i++) {
stack.pop();
}
ListNode peek = stack.peek();
peek.next = peek.next.next;
return dummyHead.next;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!