@[toc]
1.反转链表
1.1 算法题目
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
1.2 算法思路
1.设置工作指针p,来遍历链表。
2.采用头插法的方法来实现链表翻转。
1.3 代码实现
class Solution {
public ListNode reverseList(ListNode head) {
ListNode p,q;
p=head.next;
head.next=null;
while(p!=null){
q=p.next;
p.next=head.next;
head.next=p;
p=q;
}
return head;
}
}
2.回文链表
2.1 算法题目
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
2.2 算法思路
1.设置快慢指针，当快指针到达链表的末尾时，慢指针正好在链表的中间后者下一个位置。
2.通过翻转链表使得slow指针指向翻转后链表的第一个元素。同时将fast指针也指向当前链表的第一个指针。
3.通过循环判断slow指针和fast指针指向的值是否相同。2.3 代码实现
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast=head,slow=head;
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
}
if(fast!=null){
//奇数链表
slow=slow.next;
}
fast=head;
slow=reverse(slow);
while(slow!=null){
if(fast.val!=slow.val){
return false;
}
fast=fast.next;
slow=slow.next;
}
return true;
}
//翻转链表
public ListNode reverse(ListNode head){
ListNode pre=null;
while(head!=null){
ListNode next=head.next;
head.next=pre;
pre=head;
head=next;
}
return pre;
}
}
