【数据结构】_链表经典算法OJ（力扣/牛客第二弹）

目录

1. 题目1：返回倒数第k个节点

1.1 题目链接及描述

1.2 解题思路

1.3 程序

2. 题目2：链表的回文结构

2.1 题目链接及描述

2.2 解题思路

2.3 程序

1. 题目1：返回倒数第k个节点

1.1 题目链接及描述

题目链接：

面试题 02.02. 返回倒数第 k 个节点 - 力扣（LeetCode）

题目描述：

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

（该题目已保证给定k保证有效）

1.2 解题思路

思路1：计数转换为正数

遍历单链表计数，假设计得链表结点数为n，倒数第k个元素即正数第n-k个元素，再遍历返回第n-k个结点的值即可；

时间复杂度O(N)（但遍历链表两遍），空间复杂度O(1)；

思路2：存储到数组中再下标访问正数元素

新创建一个数组，遍历单链表，依次将链表的结点值记录到数组中，假设计得链表结点数为n，结点值分别记录到数组下标0~n-1的位置，返回下标为n-k的数组元素值即可；

时间复杂度O(N)，空间复杂度O(N)；

思路3：快慢指针（本题解法）

创建两个指针，一个指针指向链表第一个结点，称为慢指针；一个指针指向链表第k个结点，称为快指针；

令两个指针同时向后遍历，直至快指针指向空时，此时慢指针即指向倒数第k个结点；

时间复杂度O(N)（只遍历链表一遍），空间复杂度O(1)；

1.3 程序

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k) {
    ListNode* fast=head,*slow=head;
    // 令fast先走k步
    while(k--){
        fast=fast->next;
    }
    // 快慢同时走
    while(fast){
        slow=slow->next;
        fast=fast->next;
    }
    return slow->val;
}

2. 题目2：链表的回文结构

2.1 题目链接及描述

题目链接：链表的回文结构_牛客题霸_牛客网

题目描述：

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

2.2 解题思路

思路1：

存储到数组，再创建两个计数变量分别从前向后和从后向前进行遍历来进行回文判断。

时间复杂度：O(N)，空间复杂度：O(N)（不符合要求）；

思路2：（本题解法）

第一步：定位链表的中间结点；

第二步：从中间结点开始，将链表的后半段逆置；

第三步：创建两个指针，一个指向链表第一个结点，一个指向链表的中间结点，两个同时向后走；

对于偶数个结点的链表，直至其中一个指针指向空即可对应匹配结束：

对于奇数个结点的链表，由于逆置的后半段链表并不影响原链表中间结点的的本来指向，未逆置的前半段链表的最后一个结点的指向其实还是指向原链表的结点，最终比较也是奇数个结点链表的中间结点的自我比较，匹配结束标志仍是任意一个指针指向空：

2.3 程序

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
using ListNode = struct ListNode;
class PalindromeList {
  public:
  // 查找中间结点
    struct ListNode* middleNode(struct ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != NULL && fast->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
 // 逆置链表
    struct ListNode* reverseList(struct ListNode* head) {
        // 判空
        if (head == NULL) {
            return head;
        }
        // 创建三个指针
        ListNode* n1 = NULL;
        ListNode* n2 = head;
        ListNode* n3 = n2->next;
        while (n2) {
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if (n3)
                n3 = n3->next;

        }
        return n1;
    }
    // 判断回文
    bool chkPalindrome(ListNode* A) {
        // 查找中间链表
        ListNode* midNode=middleNode(A);
        // 逆置后半段链表
        ListNode* remidNode=reverseList(midNode);
        while(remidNode && A){
            if(remidNode->val != A->val){
                return false;
            }
            remidNode=remidNode->next;
            A=A->next;
        }
        return true;
    }
};

注：关于查找单链表中间结点、逆置链表的实现，在OJ相关文章有详解，文章链接如下：

【数据结构】_链表经典算法OJ（力扣版）-CSDN博客文章浏览阅读1.3k次，点赞33次，收藏21次。4、考虑特殊情况及相应处理：（1）原链表为空：即head=NULL，导致curNode=NULL，不会进入第一个while循环，但在newTail->next=NULL 时会导致空指针解引用操作，出现错误。故需对newTail是否为空进行单独讨论处理。（2）新链表为空：即原链表所有结点数据域的值都等于val，导致newTail->next=NULL 时会导致空指针解引用操作，出现错误。同（1）：需对newTail是否为空进行单独讨论处理。处理逻辑为：https://blog.csdn.net/m0_63299495/article/details/145355272https://blog.csdn.net/m0_63299495/article/details/145355272