题解 | #判断一个链表是否为回文结构#

核心思想

解法1： 递归方式

• 判断空链表case
• 单节点case
• 通过全局静态变量保存原始头节点
• 递归到尾节点
• 出栈方向，旧头结点和尾结点开始相向而行，比对
• 递归 # 因为给出原型函数无法实现递归，所以得另写个递归函数
  1. 得通过全局变量标记出来原始头结点
  2. 新的递归函数到尾结点
  3. 递归回程方向开始和旧头结点开始比拼，一样就给1，否则给0
     • 逆向通过出栈实现
     • 正向通过oldHead->next

缺点： 因为递归，所有空间复杂度较高，另外，最终对比的是整个链表，有点不优 优点：个人自创，写了

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param head ListNode类 the head
 * @return bool布尔型
 */

static int  isP = 0;
static struct ListNode * oldhead = NULL;
struct ListNode * judgeP(struct ListNode * head)
{
    // 尾结点
    if(head->next == NULL)
    {
        return head;
    }
    struct ListNode * tail = NULL;
    tail = judgeP(head->next);
    
    if(tail->val == oldhead->val)
    {
        isP = 1;
    }
    else
    {
        isP = 0;
    }
    oldhead = oldhead->next; 
    
    return head;
}

bool isPail(struct ListNode* head ) {
    // write code here
    if(head == NULL)
    {
        return isP;
    }
    
    if(head->next == NULL)
    {
        return 1;
    }
    
    oldhead = head;
    
    judgeP(head);
    
    return isP;
}

``` c


解法2：
- 找中间节点
  - 快慢指针方法 或 长度
    - 因需要判断奇偶性，拆分成两段独立链表，即使中间节点next需要为NULL
      故意采用求长度，一劳永逸
- 反转中间节点后面部分
- 反转后链表和原先后半段做对比

/**

• struct ListNode {
• int val;
• struct ListNode *next;
• };
• C语言声明定义全局变量请加上static，防止重复定义 */

/** *

• @param head ListNode类 the head
• @return bool布尔型 */

int get_len(struct ListNode * head) { int len = 0; while(head != NULL) { head = head->next; len++; }

return len;

}

struct ListNode * reverse(struct ListNode * head) { if(head == NULL) { return head; }

if(head->next == NULL)
{
    return head;
}

struct ListNode * newHead = NULL;
newHead = reverse(head->next);
head->next->next = head;
head->next = NULL;

return newHead;

}

_Bool isPail(struct ListNode* head ) { // write code here int listlen = get_len(head); if(listlen < 2) { return 1; }

int odd = listlen%2;
if(odd == 0)
{
    listlen = listlen/2 - 1;
}
else
{
    listlen = listlen/2;
}

int i = 0;
struct ListNode * move = head;
while(i < listlen)
{
    move = move->next;
    i++;
}

struct ListNode * slow = move->next;
move->next = NULL;
struct ListNode * newHead = reverse(slow);
while(newHead != NULL)
{
    if(newHead->val != head->val)
    {
        return 0;
    }
    newHead = newHead->next;
    head = head->next;
}
return 1;

}

####  3刷，一遍写过，更优化

/**

• struct ListNode {
• int val;
• struct ListNode *next;
• };
• C语言声明定义全局变量请加上static，防止重复定义
• C语言声明定义全局变量请加上static，防止重复定义 */

/** *

• @param head ListNode类 the head
• @return bool布尔型 */

struct ListNode * reverse(struct ListNode * head) { if(head == NULL) { return NULL; }

if(head->next == NULL)
{
    return head;
}

struct ListNode *newHead = NULL;
newHead = reverse(head->next);
head->next->next = head;
head->next = NULL;

return newHead;

}

bool isPail(struct ListNode * head) { // write code here if(head == NULL) { return 0; }

// 定义快慢指针
struct ListNode * fast = head;
struct ListNode * slow = head;

while(fast != NULL && fast->next != NULL)
{
    slow = slow->next;
    fast = fast->next->next;
}
// 牛客网上的一个bug，对输入：1，2,3，1，翻转参数是slow->next结果也是对的，传slow就是不对的
// struct ListNode * newHead = reverse(slow->next);
struct ListNode * newHead = reverse(slow);
while(newHead != NULL)
{
    if(newHead->val != head->val)
    {
        return 0;
    }
    
    newHead = newHead->next;
    head = head->next;
}

return 1;

}