【数据结构】链表经典OJ题，常见几类题型（一）

题型一：反转单链表

思路解析

反转一个链表主要是想让第一个节点指向NULL，第二个节点指向第一个，以此类推。那么我们不难想到，想要反转其中一个节点，两个指针肯定是不够的，所以这就要求我们定义三个指针：分别指向当前节点n2，前一个节点n1，后一个节点n3。

这里定义的三个指针主要作用：n1是为了能让当前节点能指向前一个节点地址，而n1就是记录前一个节点的地址，n3是为了在反转当前节点后，能找到后一个节点的地址。

那么定义一个循环后依此思路便可反转链表了。当然循环结束的条件为n3 == NULL，那么再仔细想一下，其实还有最后一个节点没有反转，此节点只需要最后单独反转便可。那么为什么不让循环结束条件为n2 == NULL呢？是因为此时n3 == n2->next而n2又等于NULL，这就导致了错误。

还要一点需要注意的是：在解题前我们还要单独判断一下此链表是否为空。

图解如下：

OJ题实例

LeetCode链接：206. 反转链表

解题代码

struct ListNode* reverseList(struct ListNode* head)
{
     //判断链表为空的情况
    if(head==NULL)
    {
        return NULL;
    }
    else
    {
         //反转链表
        struct ListNode* n1=NULL;
        struct ListNode* n2=head;
        struct ListNode* n3=head->next;
        while(n3)
        {
            n2->next=n1;
            n1=n2;
            n2=n3;
            n3=n3->next;
        }
        //最后一个节点的判断
        n2->next=n1;
        return n2;
    }
}

题型二：快慢指针

思路解析

通常快慢指针方法出现在需要找链表中间节点，链表带环等题型中。快慢指针的逻辑思路如下：

先定义两个结构体指针struct ListNode* slow = head, *fast = head;，先将他们指向头节点，在写一个循环，每次循环慢指针向后走一个节点，即slow = slow->next;，快指针向后走两个节点，即fast = fast->next->next;，循环的判断条件为fast != NULL && fast->next != NULL，这样便很好解决了链表为空和只有一个节点的情况。需要注意的是如果节点数为奇slow刚好在中间节点，节点数为偶slow在中间两个节点的后一个。

OJ题实例

LeetCode链接: 876. 链表的中间结点

解题代码

struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* fast=head, *slow=head;
    while(fast && fast->next)
    {
        slow = slow -> next;
        fast = fast -> next -> next;
    }
    return slow;
}

两类题型的结合

牛客链接: OR36 链表的回文结构

解题思路：此题可以先找到中间节点，然后把后半部分逆置，然后进行前后两部分一一比对，如果节点的值全部相同，则即为回文。

class PalindromeList {
public:
  bool chkPalindrome(ListNode* A) {
    if (A == NULL || A->next == NULL)
      return true;
    ListNode* slow, *fast, *prev, *cur, *nxt;
    slow = fast = A;
    //找到中间节点，即题型二快慢指针
    while (fast && fast->next)
    {
      slow = slow->next;
      fast = fast->next->next;
    }
    prev = NULL;
    //后半部分逆置，即题型一链反转
    cur = slow;
    while (cur)
    {
      nxt = cur->next;
      cur->next = prev;
      prev = cur;
      cur = nxt;
    }
    //逐点比对
    while (A && prev)
    {
      if (A->val != prev->val)
        return false;
      A = A->next;
      prev = prev->next;
    }
    return true;
  }
};