本周（5.18-5.25）写了探索初级算法的三个板块（数组 字符串 链表）的题目的内容外加一些的每日一题。总结一下几个比较有意思的题目。

链表

数组这块的内容比较杂，有些题目使用的是双指针的操作，有些题目使用的是位运算的性质。链表其中的快慢指针用的比较多，下面列举两个题目进行一个基础操作的总结：

快慢指针的基本使用

将链表分成两个部分

慢指针和快指针同时从首节点出发，快指针一次走两个节点，慢指针一次走一个节点，先给代码：

            ListNode slow = head;
            ListNode fast = head;
            while(fast.next != null && fast.next.next != null){
                fast = fast.next.next;
                slow = slow.next;
            }

当链表的节点个数为奇数时

显然，当快指针不能再走的时候，慢指针必然指向链表的中心

当链表的节点个数为偶数时

显然，slow.next不论在节点为奇数还是偶数时都指的是链表的后1/2的部分，这一点在判断链表是否是回文链表时非常有用。

2. 判断链表是否存在回环

如果存在回环

如果链表存在回环，那么链表的快慢指针一定会在某一个地方相遇：

环形链表

环形链表

 class Solution {
        public boolean hasCycle(ListNode head) {
            if(head == null || head.next == null) return false;
            ListNode slow = head;
            ListNode fast = head.next;
            while(slow != fast){
                if(fast == null || fast.next == null) return false;
                slow = slow.next;
                fast = fast.next.next;
            }
            return true;
        }
    }

回文链表

回文链表
这道题如果将整个链表遍历存放到数组，然后使用双指针进行对比数组判断是否是回文，会造成内存溢出的问题。为了解决这个问题，我们可以使用翻转链表+快慢指针的策略

反转链表

翻转链表有两种方法：

头插法

头插法

然后就按照这种方法继续就可以实现头插过程，最终返回的时候

return dummy.next;

就完事了。
但是这种方法，在这题中，会使用而外的内存空间，也可能会导致内存溢出。

交换记录法

这个操作的核心是：

1. cur的下一个节点使用temp保存，因为cur.next之后要使用pre赋值

2. cur.next = pre；
   完成这两个步骤之后，cur就变成pre（pre = cur），即变成下一轮迭代中的上一个位置，且cur向下移动（cur = temp）；
   具体的操作如图：

   
   初始

ListNode temp = cur.next cur.next = pre pre = cur; cur = temp;

代码如下：

 public ListNode reverseList(ListNode head){
            ListNode cur = head;
            ListNode pre=  null;
            while(cur != null){
                ListNode temp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = temp;
            }
            return pre;
        }

快慢指针

使用快慢指针找到具体的1/2的位置

 public ListNode findFirstHalf(ListNode head){
            ListNode slow = head;
            ListNode fast = head;
            while(fast.next != null && fast.next.next != null){
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow;
        }

显然，不管链表的长度是奇数还是偶数，slow.next总是需要比较的下一半。因为中间的那个节点不需要比较（长度为奇数时）。
完整代码：

 static class Solution {
        public boolean isPalindrome(ListNode head) {
            if(head == null || head.next == null) return true;
            ListNode firstHalfEnd = findFirstHalf(head);
            ListNode secondHalfEnd = reverseList(firstHalfEnd.next);

            ListNode p = head;
            ListNode q = secondHalfEnd;
            while(p != null && q != null){
                if(p.val != q.val) return false;
                p = p.next;
                q = q.next;
            }
            return true;
        }

        public ListNode findFirstHalf(ListNode head){
            ListNode slow = head;
            ListNode fast = head;
            while(fast.next != null && fast.next.next != null){
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow;
        }

        public ListNode reverseList(ListNode head){
            ListNode cur = head;
            ListNode pre=  null;
            while(cur != null){
                ListNode temp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = temp;
            }
            return pre;
        }

    }