206. Reverse Linked List

206. 反转链表问题

其实这个是很简单的一个问题，但是可能由于对于链表这种数据结构不太熟悉。导致做起来有点困难。

问题描述

就不用描述了，就是一个反转。
1->2->3->4->Null 变成 Null->4->3->2->1 (这里可以不用看这个 Null)

问题分析

解题思路

从前向后遍历，要反转，就要打断。比如需要节点2的下一个节点是1，即 2->1，那么2和3之间必须就要打断。那么在打断之前就要将遍历到节点3。
所以核心思路是：维护两个节点 “前-中”，在每次遍历时候 添加一个 “后”节点，通过这个“后”节点来保证上面说的可以遍历到下一个节点。而“前-中”两个节点则是为了反向。

代码

ListNode pre = null;
          while (head!=null){
              ListNode nextNode = head.next;
              head.next = pre;    // 这个时候已经打断了
              pre = head; // 更新
              head = nextNode; // 保证可以到下一个节点
          }
          return pre;

234. 回文链表

这个题目，就不多说了。
是在上面的反转链表的基础上来的。
核心有两点：

1. 找到链表中点
   这里有一个 快慢双指针法。
   就是通过一个快指针每次走2个，慢指针每次走1个，最终二者都不超过（实际上是快指针）长度，慢指针所在的位置就是中点。
   然后从中点向后反转后半个链表。
   将前半个链表和反转后的后半个链表一一比较。
2. 反转链表
   跟上面说的一样。