Farenew的博客

2019.07.15

1. 快慢指针

当题目中的数据以链表的形式进行存储时,与字符串的形式相比,由于链表不存在下标,也就意味着找到数据的中点就变得相对困难。因此,使用快慢指针在这里就显得格外的便捷:

  • 首先我们设置两个指针slow和fast,slow指针每次移动一步,fast指针每次移动两步;
  • 如果链表中节点个数为偶数时,当快指针无法继续移动时,慢指针刚好指向中点;如果链表中节点个数为奇数时,当快指针走完,慢指针指向中点前一个节点。

快慢指针可以应用的题:

回文判断

方法是使用快慢指针遍历整个链表. 并且把慢指针的内容push到栈中, 然后在遍历结束的时候. 此时从中点开始, 把栈中的元素pop出来, 并且和中点以后的元素进行对比即可.

题目参考: leetcode 234

解答:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(!head||!head->next)
            return true;
        ListNode *slow=head,*fast=head;
        stack<int> s;
        s.push(head->val);
        while(fast->next&&fast->next->next)
        {
            slow=slow->next;
            fast=fast->next->next;
            s.push(slow->val);      //将慢指针指向的数据依次压入栈中
        }
        if(!fast->next)             //说明快指针走到头了,节点个数为奇数,此时慢指针指向中点数字
            s.pop();                //将中点pop掉
        while(slow->next)           //依次将中点两侧数据进行比较
        {
            slow=slow->next;
            int tmp=s.top();
            s.pop();
            if(tmp!=slow->val)
                return false;
        }
        return true;
    }
};

这里的内容是转载自【LeetCode刷题笔记】链表与快慢指针

环判断

快慢指针还可以用来判断链表是否有环, 有的话则快慢指针一定会相遇!

2. 判断两个链表是否相交

编程判断俩个链表是否相交

给出俩个单向链表的头指针,比如h1,h2,判断这俩个链表是否相交。为了简化问题,我们假设俩个链表均不带环。

解法

两个链表相交,则从某一个点以后,两个链表的值全部相等。两个链表的形状像是一个Y字形. 注意它们在相交后, 后面内容一定完全一致的.

解题方法:

  • 遍历两个链表, 求得它们的长度和长度差D
  • 长链表从D处开始, 短链表从头开始遍历. 然后找到相等直到尾部的节点, 这个节点就是交点.