这篇文章对简单题的前三百题中链表TAG做一个总结，下面来看下本次总结的题目列表：
1. 141 环型链表
2. 203 移除链表元素
3. 206 反转链表
4. 234 回文链表
5. 237 删除链表中的结点
141 环型链表
题目大意
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
方法一：哈希表
遍历链表，检查当前节点是否在哈希表中，若存在，说明有循环；若不存在，将这个结点加入哈希表中。
public boolean hasCycle(ListNode head) {
Set<ListNode> set = new HashSet<>();
for(;head!=null;head=head.next) {
if(set.contains(head)) return true;
else set.add(head);
}
return false;
}
方法二：快慢指针
设置两个指针，快指针从head.next出发，慢指针从head出发。想象两个在跑步，一个跑的快，一个跑的慢，他们的终点相同，但是跑得快的人起点离终点更近。如果赛道不循环，那么跑得慢的人一定追不上跑的快的人。
public static boolean hasCycle(ListNode head) {
if(head==null || head.next == null) return false;
ListNode slow = head;
ListNode fast = head.next;
for(;slow!=fast;slow = slow.next,fast = fast.next.next)
if(fast==null || fast.next ==null) return false;
return true;
}
运行时间1ms。
203 移除链表元素
题目大意
删除链表中等于给定值 val 的所有节点。
示例:
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
思路
题目要求删除链表中所有val值的结点，可以改变链表的结构。可以用递归或者迭代实现。
方法一：递归
运行时间2ms。
public ListNode removeElements(ListNode head, int val) {
if(head==null) return null;
head.next = removeElements(head.next,val);
if(head.val == val) return head.next;
else return head;
}
方法二：迭代
这里出于删除结点的方便，设置了一个虚拟头结点。并且需要记录当前结点的前一个结点pre。
public ListNode removeElements(ListNode head, int val) {
if(head == null) return null;
ListNode ahead = new ListNode(val-1);
ahead.next = head;
ListNode pre = ahead,cur=head;
while(cur!=null) {
if(cur.val == val) {
pre.next = cur.next; //删除结点时pre是不移动的
cur = cur.next;
}else {
pre=cur;
cur=cur.next;
}
}
return ahead.next;
}
运行时间2ms。
206 反转链表
题目大意
反转一个单链表。
示例：
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
方法一：递归
递归函数返回的是反转以后需要链接的那个结点。运行时间1ms。
public ListNode reverseList(ListNode head) {
if(head==null||head.next ==null) return head;
ListNode pre = reverseList(head.next);
head.next.next = head;
head.next = null;
return pre;
}
注意这里指针的反转是怎么写的：head.next.next = head。head.next = null消除了循环。
方法二：迭代
利用迭代的方法遍历链表时，在反转之前需要先记录下一轮处理的结点。运行时间1ms。
public ListNode reverseList(ListNode head) {
if(head==null || head.next ==null) return head;
ListNode pre = null;
ListNode cur = head;
while(cur!=null) {
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
234 回文链表
题目大意
请判断一个链表是否为回文链表。
示例1：
输入: 1->2
输出: false
示例2：
输入: 1->2->2->1
输出: true
方法一：头插法
利用头插法建立新的链表，然后将新链表与旧链表对比。这样的空间复杂度为O（n）,时间复杂度为O（n+n）。
public boolean isPalindrome(ListNode head) {
ListNode heada = new ListNode(0);
ListNode headb = head;
while(headb!=null) //头插法
{
ListNode p = new ListNode(headb.val);
p.next = heada.next;
heada.next = p;
headb=headb.next;
}
for(heada=heada.next;head!=null;heada=heada.next,head=head.next)
if(head.val!=heada.val) return false;
return true;
}
运行时间5ms。
方法二：StringBuilder字符串反转
运行时间9ms。
public boolean isPalindrome(ListNode head) {
StringBuilder sb = new StringBuilder();
while(head!=null) {
sb.append(head.val+'0');
head=head.next;
}
return sb.toString().equals(sb.reverse().toString());
}
注意：int转化为char, +'0'。 char转int -'0'。
方法三：快慢指针+反转一半链表
如果能找到链表的中点，就可以对两边进行比较，那么只需要一次遍历就可以得出结果。关于寻找中点，利用的是快慢指针，fast指针的移动速度为2，慢指针移动速度为1。当fast指针移动到链表尾部，slow指针指向链表中点。（但链表长度奇偶数情况需要最后讨论）
public boolean isPalindrome(ListNode head) {
if(head==null) return true;
ListNode slow = head,fast = head,pre=null,temp=null;
while(fast!=null && fast.next!=null)
{
fast = fast.next.next;
temp = slow.next;
slow.next = pre;
pre = slow;
slow = temp;
}
fast = fast == null?slow:slow.next; //处理奇数偶数的不同
slow = pre;
for(;slow!=null && fast!=null;slow=slow.next,fast=fast.next)
if(slow.val!=fast.val) return false;
return true;
}
运行时间1ms。
