Leetcode.19 删除链表的倒数第N个节点

1. 思路

• 扫描一次计算长度
• 使用栈

• 使用双指针

  • 思路就是倒数第N个就是正数第L-N个。
  • 第一个指针，遍历n个节点，记录正数第N个第位置
  • 第二个指针从头开始与第一个指针继续往下遍历，当第一个指针遍历到链表尾部，则第二个指针正好停留在正数L-N 上。

    2. 代码

    ```java public class RemoveNthFromEnd {

  public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(-1); dummy.next = head; ListNode first = head; ListNode second = dummy; for (int i = 0; i < n; i++) {

  first = first.next;

  } while (first != null) {

  first = first.next;
  second = second.next;
  

  } second.next = second.next.next; return dummy.next; } } ```

  Leetcode.82 删除排序链表中的重复元素 II

  1. 思路

• 定义一个虚拟节点dummy连接头部，pre = dummy cur = head

• 使用记数来看重复多少个节点，最后跳过所有重复的节点将pre.next = next

  2. 代码

  class Solution {
  public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;
        while (cur!=null){
            int num = 0;
            ListNode next = cur.next;
            while (next!=null&&next.val==cur.val){
                next = next.next;
                num++;
            }
            if(num>0){
                pre.next = next;
                cur = next;
  
            }else {
                pre = cur;
                cur = next;
            }
        }
        return dummy.next;
    }
  }