链表

1、给一个链表，删除倒数第n个节点，然后返回头结点，要求一趟遍历解决问题。

1->2->3->4->5 n=2 执行完删除返回1->2->3->5
解题思路：
首先想到的肯定是遍历一次获取到长度，然后根据长度-n删除倒数第n个节点，但题目要求一趟遍历。
链表里面常见的几种方法中有一种就是快慢指针！
让一个指针比另一个指针慢n步，当快指针到链表尾部的时候慢指针刚好到第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) {
        ListNode start = new ListNode(-1);
        start.next = head;
        //快指针先走到n的位置
        for(int i=0;i<n;i++){
            head = head.next;
        }
        ListNode newHead = start;
        //慢指针和快指针一起往前走，直到快指针走到尾
        while(head!=null){
            newHead = newHead.next;
            head = head.next;
        }
        newHead.next = newHead.next.next;
        return start.next;
        
    }
}

2、翻转链表

给一个链表，翻转头尾顺序，并返回新的头
解题思路：
每次取一个头下来指向旧的头，先搞个缓存pre

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        while(head!=null){
            ListNode temp = head.next;
            head.next = pre;
            pre = head;
            head = temp;
        }
        return pre;
    }
}

3、只给一个节点，删除这个节点

1->2->3->4 给一个3，删除三
解题思路：
把后一个节点的值赋给当前节点，然后把后一个节点删除就行

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        ListNode next = node.next;
        if(next == null){
            node.next = null;
            node=null;
            return;
        }
        int val = next.val;
        node.val = val;
        node.next = next.next;
    }
}