19. 刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)
給定一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)節(jié)點(diǎn)副女，并且返回鏈表的頭結(jié)點(diǎn)微宝。
示例：
給定一個(gè)鏈表: 1->2->3->4->5, 和 n = 2.
當(dāng)刪除了倒數(shù)第二個(gè)節(jié)點(diǎn)后炉峰，鏈表變?yōu)?1->2->3->5.
說(shuō)明：
給定的 n 保證是有效的复颈。
進(jìn)階：
你能嘗試使用一趟掃描實(shí)現(xiàn)嗎蚓曼？
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有亲澡。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處纫版。
-
1.兩次遍歷算法
思路：
1.計(jì)算出整個(gè)鏈表的長(zhǎng)度size
2.找出要?jiǎng)h除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
3.刪除節(jié)點(diǎn)即可
public static class ListNode {
private int val;
private ListNode next;
public ListNode(int val) {
this.val = val;
}
//用于測(cè)試用例
public ListNode(int[] arr) {
if (arr == null || arr.length == 0) throw new NullPointerException("array is Empty");
this.val = arr[0];
ListNode cur = this;
for (int i = 1; i < arr.length; i++) {
cur.next = new ListNode(arr[i]);
cur = cur.next;
}
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
ListNode cur = this;
while (cur != null) {
res.append(cur.val + "->");
cur = cur.next;
}
res.append("NULL");
return res.toString();
}
}
public static ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null) return null;
ListNode cur = head;
int size = 0;
while (cur != null) {
size++;
cur = cur.next;
}
if (n == size) return head.next;
else if (n > size) return head;
int index = size - n - 1;
cur = head;
for (int i = 0; i < index; i++) {
cur = cur.next;
}
ListNode retNode = cur.next;
cur.next = retNode.next;
retNode.next = null;
return head;
}
復(fù)雜度分析：
時(shí)間復(fù)雜度：O(L),假設(shè)鏈表長(zhǎng)度為L(zhǎng)床绪，該算法對(duì)鏈表進(jìn)行了兩次遍歷，實(shí)際操作執(zhí)行了 2L - n
空間復(fù)雜度：O(1),我們只用了常量級(jí)的額外空間其弊。
-
2.使用虛擬頭節(jié)點(diǎn)
思路：
和方法 1 類似癞己，只是使用了一個(gè)虛擬頭節(jié)點(diǎn)
public static ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null) return null;
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
int length = 0;
ListNode cur = head;
while (cur != null) {
length++;
cur = cur.next;
}
length -= n;
ListNode prev = dummyHead;
while (length > 0) {
length--;
prev = prev.next;
}
prev.next = prev.next.next;
return dummyHead.next;
}
復(fù)雜度分析：
時(shí)間復(fù)雜度：O(L),假設(shè)鏈表長(zhǎng)度為L(zhǎng)，該算法對(duì)鏈表進(jìn)行了兩次遍歷梭伐，實(shí)際操作執(zhí)行了 2L - n
空間復(fù)雜度：O(1),我們只用了常量級(jí)的額外空間痹雅。
-
3.雙指針?lè)?/h4>
思路：
1.創(chuàng)建一個(gè)虛擬頭節(jié)點(diǎn)dummyHead, 兩個(gè)指針first、second并都指向虛擬頭節(jié)點(diǎn)
2.first先移動(dòng)n+1次糊识，然后兩個(gè)節(jié)點(diǎn)同時(shí)移動(dòng)绩社，直到first == null，這時(shí)候second指向的就是待刪除節(jié)點(diǎn)的前一個(gè)
public static ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode first = dummyHead;
ListNode second = dummyHead;
for (int i = 1; i <= n + 1; i++) {
first = first.next;
}
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummyHead.next;
}
復(fù)雜度分析：
時(shí)間復(fù)雜度：O(L),該算法對(duì)含有 L 個(gè)結(jié)點(diǎn)的列表進(jìn)行了一次遍歷赂苗。因此時(shí)間復(fù)雜度為 O(L)铃将。
空間復(fù)雜度：O(1),我們只用了常量級(jí)的額外空間。
-
測(cè)試用例
public static void main(String[] args) {
int[] arr = new int[] {1, 2, 3, 4, 5};
ListNode listNode = new ListNode(arr);
System.out.println(listNode);
System.out.println("刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)" + removeNthFromEnd3(listNode, 2));
}
-
結(jié)果
1->2->3->4->5->NULL
刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)1->2->3->5->NULL
-
源碼
-
我會(huì)隨時(shí)更新新的算法哑梳，并盡可能嘗試不同解法劲阎，如果發(fā)現(xiàn)問(wèn)題請(qǐng)指正
- Github
