链表

链表是最基本的数据结构，面试官也常常用链表来考察面试者的基本能力，而且链表相关的操作相对而言比较简单，也适合考察写代码的能力。链表的操作也离不开指针，指针又很容易导致出错。

综合多方面的原因，链表题目在面试中占据着很重要的地位。

public class ListNode {      int val;      ListNode next;      ListNode(int x) {          val = x;          next = null;     } }

删除节点

思路：

• 将下一个节点复制到当前

public void deleteNode(ListNode node) {     if (node.next == null){         node = null;         return;     }     // 取缔下一节点     node.val = node.next.val     node.next = node.next.next }

翻转链表

思路

思路：每次都将原第一个结点之后的那个结点放在新的表头后面。
比如1,2,3,4,5

• 第一次：把第一个结点1后边的结点2放到新表头后面，变成2,1,3,4,5
• 第二次：把第一个结点1后边的结点3放到新表头后面，变成3,2,1,4,5
• ……
• 直到： 第一个结点1，后边没有结点为止。

视频

大圣算法 翻转链表(Reverse Linked List ) -- LeetCode 206

public ListNode reverse(ListNode head) {     //prev表示前继节点     ListNode prev = null;     while (head != null) {         //temp记录下一个节点，head是当前节点         ListNode temp = head.next;         head.next = prev;         prev = head;         head = temp;     }     return prev; }

中间元素