力扣算题【第二期】

@[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;
    }
}