单链表寻找是否有环及环位置

只确定是否有环的情况

确定一个单链表中是否有环,如果有的话找出环连接到的节点的位置,如果没有就返回NULL.这道题我记得好像看到别人在面试题中见到过,如果只是单纯的找是否有环的话还是很简单的.

struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x): val(x), next(NULL) {}
}
bool hasCycle(ListNode *head)
{
  if(head == NULL)
    return false;
  ListNode *slowNode,*fastNode;
  slowNode = fastNode = head;
  while(fastNode->next && fastNode->next->next)
  {
    slowNode = slowNode->next;
   fastNode = fastNode->next->next;
    if(slowNode == fastNode)
      return true;
  }
  return false;
}

主要的思路是用一个快指针和慢指针,快指针一次走两步,慢指针一次只走一步,如果链表中有环的话快慢指针肯定会相遇,即可判断链表中是否有环.接下来简单解释下如果寻找环起始位置的原理,我们可以简单思考下快指针和慢指针相遇位置的特殊性,在什么情况下快慢指针会相遇呢?
我的答案是当快慢指针都进入环中,就形成了快指针追逐慢指针的过程.而当慢指针进入环中,快指针比慢指针多走了多少呢?
在回答这个问题之前,我们先做一些假设:我们认为从头节点到环开始节点的距离为n,环的大小为m.
显然当慢指针到达环开始节点时,快指针在慢指针前面n % m的位置,假设n % m为k吧,也等价于,快指针在慢指针后面m - k位置处,所以需要m - k的单位时间才能追上慢指针,这个时候,慢指针到哪的呢?
显然,是距离环开始节点k的节点,这个时候我们又注意到,头节点到环开始节点的距离n = ((int)(n / m))*m + k.所以问题的关键就出来了,如果有两个指针,一个从快慢指针相遇的位置出发,另一个指针从头节点出发,他们将会在环开始节点的位置相遇!!至此,我们的问题就已经完美的解决了,下面贴一些代码.

 ListNode *detectCycle(ListNode *head)
{
    if(head == NULL || head->next == NULL)
        return NULL;
    ListNode *slowNode, *fastNode;
    slowNode = fastNode = head;
    while(fastNode->next && fastNode->next->next)
    {
        slowNode = slowNode->next;
        fastNode = fastNode->next->next;
        if(slowNode == fastNode)
        {
            slowNode = head;
            while(slowNode != fastNode)
            {
                slowNode = slowNode->next;
                fastNode = fastNode->next;

            }
            return fastNode;

        }

    }
    return NULL;
}

探测一个单链表是否为回文序列

这个和上一道题有一点点相似之处吧,解决这个问题的思路不算直接,我们需要先找到单链表的中点(不一定是严格意义上的中点),然后翻转单链表的后半部分,再比较链表的前半部分和后半部分,如果完全相同就是回文链表,否则不是.

• 先获得一个单链表的中点位置,这个问题是不是感到很熟悉,答案正是我们在上一题用到的快慢指针,对于一个单链表,当快指针到达链表的尾部时,慢指针恰好到达链表的中点.不过需要注意的是,当一个单链表具有偶数个节点时,快指针实际上会在尾节点的前一个节点停下,这个时候我们就需要将块指针和慢指针同时向后移一个节点,大家可以画图看一下,并不难理解.
• 第二点就是我们需要翻转一个单链表,我个人的思路如下:需要一个头指针first指向已经翻转过的链表的头节点,需要一个尾指针last指向已经翻转过的链表的尾节点(初始时未翻转,头指针和尾指针都指向待翻转链表的头结点),另外需要一个temp指针用来暂存一下额外的信息.
• 主要思路为

temp = last->next;//temp储存需要翻转的节点的指针
last->next = last->next->next;
temp->next = first;//把需要翻转的节点放在开始位置
first = temp;//使头指针始终指向第一个节点

上面只是思路,没考虑是否已经到链表尾部的情况,下面贴出代码

struct ListNode
{
  int val;
  ListNode *next;
  ListNode(int x):val(x),next(NULL){}
}

bool isPalindrome(ListNode *head) {
  if (head == NULL || head->next == NULL)
    return true;
  ListNode *slow, *fast;
  fast = slow = head;
  while (fast->next && fast->next->next) {
    slow = slow->next;
    fast = fast->next->next;
  }
  // in case that the fast pointer doesn't reach the end of list
  if (fast->next != NULL) {
    fast = fast->next;
    slow = slow->next;
  }
  // reverse the later half of the list.
  ListNode *first, *last;
  first = last = slow;
  ListNode *temp;
  while (last->next != NULL) {
    temp = last->next;
    last->next = last->next->next;
    temp->next = first;
    first = temp;
  }
  // reverse done, and then we compare the two list.
  while (head != slow) {
    if (first->val != head->val)
      return false;
    head = head->next;
    first = first->next;
  }
  return true;
}

实际上这个问题有很多衍生的版本,但是基本思路都是这个,我就不再一一细说了.