题目分析
原题链接,登陆 LeetCode 后可用
这道题是让我们用一遍遍历删掉链表的倒数第 N 个结点.这道题也是快慢指针的又一个典型的应用.我们让快指针比慢指针快 N 步,然后让快慢指针一起往后走即可.这里我考虑了一种特殊情况,就是删掉倒数第一个结点.删掉这个结点,我采用了特殊的方式.但是算法整体上仍然是一趟遍历,时间复杂度仍然为 O(n).
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if(head == null || head.next == null) {
return null;
}
if(n == 1) {
ListNode temp = head;
while(temp.next.next != null) {
temp = temp.next;
}
temp.next = null;
} else {
ListNode fast = head;
ListNode slow = head;
while(n > 0) {
fast = fast.next;
n--;
}
while(fast != null) {
fast = fast.next;
slow = slow.next;
}
slow.val = slow.next.val;
slow.next = slow.next.next;
}
return head;
}
}
来源: http://www.jianshu.com/p/3423477930fa