单链表题带刷（二）

目录

一、链表的回文结构

1.1 题目

1.2 解题思路

二、相交链表

2.1 题目

一、链表的回文结构

1.1 题目

https://www.nowcoder.com/share/jump/6870342311730273670970https://www.nowcoder.com/share/jump/6870342311730273670970

1.2 解题思路

思路一：创建新链表，将原链表反转并保存在新链表里，在将新旧链表比较

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
#include <cstddef>
class PalindromeList 
{
public:
    bool chkPalindrome(ListNode* A) 
    {
        struct ListNode* ne = A;
       struct ListNode* n1 = NULL;
       struct ListNode* n2 = ne;
       struct ListNode* n3 = ne->next;
       while(n2)
       {
          n2->next = n1 ;
          n1 = n2;
          n2 = n3;
          if(n3)
          {
             n3 = n3->next;
          }
       }
       while(A)
       {
         if((n1->val)!=(A->val))
         {
            return false;
         }
          A = A->next;
          n1 = n1->next;
       }
       return true;
    }
};

思路二：将链表中的数值存储到数组当中；在进行比较

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) 
    {
        int arr[900] = {0};
        int i = 0;
        while(A)
        {
           arr[i++] = A->val;
           A = A->next;
        }
        int left = 0;
        int right = i-1;
        while(right>left)
        {
          if(arr[right]!=arr[left])
          { 
             return false;
          }
          right--;
          left++;
        }
        return true;
    }
};

思路三： 找中间结点（快慢指针，详情请看第一篇文章），反转以中间结点为头的链表(反转指针，详情看第一篇文章)，遍历原链表和以中间节点为头的链表

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:
    bool chkPalindrome(ListNode* A)
    {
       ListNode* fast = A;
       ListNode* slow = A;
       while(fast&&fast->next)
       {
         slow = slow->next;
         fast = fast->next->next;
       }
       ListNode* n1 = NULL;
       ListNode* n2 = slow;
       ListNode* n3 = slow->next;
       while(n2)
       {
          n2->next = n1;
          n1 = n2;
          n2 = n3;
          if(n3)
          n3 = n3->next;
       }
       ListNode* prev = A;
       while(prev!=slow)
       {
          if((prev->val)!=(n1->val))
          return false;
          prev = prev->next;
          n1 = n1->next;
       }
       return true;
    }
};

二、相交链表

2.1 题目

https://leetcode.cn/problems/intersection-of-two-linked-listshttps://leetcode.cn/problems/intersection-of-two-linked-lists

2.2 解题思路

因为链表一旦相交那么他们从相交点后的链表一定是一样的，所以链表的长度差只在相交点前，我们先遍历链表找出他们的长度差，然后保证他们遍历时长度是一样的。但他们的下一个节点都是相同的时候相同点就是相交点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    ListNode* n1 = headA;
    ListNode* n2 = headB;
    int sizeA = 0;
    int sizeB = 0;
    while(n1)
    {
       sizeA++;
       n1 = n1->next;
    }
     while(n2)
    {
       sizeB++;
       n2 = n2->next;
    }
    int gap = abs(sizeA-sizeB);
    ListNode* longlist = headA;
    ListNode* shortlist = headB;
    if(sizeB>sizeA)
    {
        longlist = headB;
        shortlist = headA;
    }
    while(gap--)
    {
        longlist = longlist->next;
    }
    while(longlist)
    {
        if(longlist==shortlist)
        return longlist;
        longlist = longlist->next;
        shortlist = shortlist->next;
    }
    return NULL;
}