leetcode [#19]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

Given a linked list, remove the nth node from the end of list and return its head.

Example:
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

---

解决方案

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null) return null;
        ListNode p = head;
        int num = 0;
        while(p != null){
            num++;
            p = p.next;
        }

        p = head;

        if(num - n ==0){
            head = head.next;
            return head;
        }
        int temp = 0;
        while(p != null){
            temp++;
            if(temp == (num-n)){
                if(p.next != null){
                    p.next = p.next.next;
                }
            }
            p = p.next;
        }
        return head;
    }
}

---

注意事项

1. 首先获取链表长度，之后删除指定节点就很简单。
2. 但题目要求在一次遍历中解决问题，故如下方法更好：

   /** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */
    * Definition for singly-linked list.
    * public class ListNode {
    *     int val;
    *     ListNode next;
    *     ListNode(int x) { val = x; }
    * }
    */
   public class Solution {
       public ListNode removeNthFromEnd(ListNode head, int n) {
           if(head == null) return null;
           
           ListNode fakeHead = new ListNode(0);
           fakeHead.next = head;
           ListNode p = fakeHead;
           
           List<ListNode> list = new ArrayList<>();
   
           while(p != null){
               list.add(p);
               if(list.size() > (n+1)){
                   list.remove(0);
               }
               p = p.next;
           }
           list.get(0).next = list.get(1).next;
           return fakeHead.next;
       }
   }

其思路是：

使用了一个长度为(n+1)的ArrayList作为“滑动窗口”，这样遍历一遍链表，遍历结束时，list就会装着最后(n+1)个节点，所以要删除的是list中的第二个节点，因此只要将list中第一个节点指向第二个节点后面的内容即可（可能是null）。另外，还要注意使用了“头指针”，去除第一个节点的特殊性。