当前位置：首页 > news >正文

LeetCode/NowCoder-链表经典算法OJ练习3

news 来源：原创 2024/9/22 10:38:05

孜孜不倦：孜孜：勤勉，不懈怠。指工作或学习勤奋不知疲倦。💓💓💓

说在前面

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

题目二：链表的回文结构

题目三：相交链表

SUMUP结尾

说在前面

dear朋友们大家好！💖💖💖数据结构的学习离不开刷题，在对链表的相关OJ进行练习后又更新复杂度的OJ，这并不意味这链表的题目就结束了，我们今天就继续联系链表相关的OJ练习。当今天我们的题目除了LeetCode，还来自NowCoder。

👇👇👇

友友们！🎉🎉🎉点击这里进入力扣leetcode学习🎉🎉🎉

以下是leetcode题库界面：

👇👇👇

🎉🎉🎉点击这里进入牛客网NowCoder刷题学习🎉🎉🎉
以下是NowCoder题库界面：

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

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

题目描述：

题目分析：

思路1：将创建一个数组temp，将链表中节点的地址存入数组temp，再返回数组中下标为n-k的地址所指向的数据。

举例：1->2->3->4->5->6 和 k = 3

代码如下：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
#define numsSize 100
typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k) {ListNode* pcur = head;ListNode* temp[numsSize];//创建临时数组int i = 0;while (pcur != NULL)//将链表节点地址存入数组temp{temp[i++] = pcur;pcur = pcur->next;}return temp[i - k]->val;//返回倒数第k个节点的数据
}

不过，假设链表很长，此时空间复杂度就会比较高，所以用numsSize固定长度显然不是好的办法，应该用动态内存分配的办法来初始化temp

代码如下：

 /*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
int kthToLast(struct ListNode* head, int k) {ListNode* pcur = head;int length = 0;while (pcur != NULL)//遍历数组，得到节点的个数{length++;pcur = pcur->next;}//动态创建二级指针变量tempListNode** temp = (ListNode**)malloc(length * sizeof(ListNode*));pcur = head;int i = 0;while (pcur != NULL)//将链表节点地址存入temp{temp[i++] = pcur;pcur = pcur->next;}return temp[i - k]->val;//返回倒数第k个节点的数据
}

不过显然空间复杂度为O(N)，不是一个非常好的办法。如果给出前提条件：空间复杂度为O(1)，这个方法就不行了。

思路2：将创快慢指针法：定义快慢指针fast、slow，先让fast走k步，再让slow和fast同时走，这样当fast走完slow刚好指向倒数第k个节点。

举例：1->2->3->4->5->6 和 k = 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* slow = head;ListNode* fast = head;while (k--)//让fast先走k步{fast = fast->next;}//当fast走完，此时slow指向的就是倒数第k个节点while (fast != NULL){fast = fast->next;slow = slow->next;}return slow->val;
}

题目二：链表的回文结构

题目链接：链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

题目描述：

题目分析：

思路：先找到链表的中间节点，再将链表的后半部分反转，比较前半部分和后半部分的元素是否相等。

我们需要用到之前OJ练习1中的两个函数：

1.链表的中间节点：876. 链表的中间结点 - 力扣（LeetCode）

2.反转链表：206. 反转链表 - 力扣（LeetCode）

如果忘记了，大家点击这里复习：LeetCode/NowCoder-链表经典算法OJ练习1

代码如下：

/*struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public://寻找链表的中间节点struct ListNode* middleNode(struct ListNode* head){struct ListNode* slow = head;struct ListNode* fast = head;while (fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}//反转链表struct ListNode* reverseList(struct ListNode* head) {if (head == NULL)return NULL;struct ListNode* n1 = NULL;struct ListNode* n2 = head;struct ListNode* n3 = head->next;while (n2){n2->next = n1;n1 = n2;n2 = n3;if (n3)n3 = n3->next;}return n1;}bool chkPalindrome(ListNode* A) {//寻找链表的中间节点struct ListNode* mid = middleNode(A);//反转链表后半段struct ListNode* rmid = reverseList(mid);while (rmid && A)//比较前后段是否相同{if (rmid->val != A->val)return false;rmid = rmid->next;A = A->next;}return true;}
};

像这种题属于组合体，比较综合，同时也告诉我们具有一定功能的代码在下次使用时可以稍加修改再Ctrl+C/V，可以省去很多麻烦，也比较方便。

题目三：相交链表

题目链接：160. 相交链表 - 力扣（LeetCode）

题目描述：

题目分析：

思路：这题比较复杂，我们需要模块化思考。同时注意单链表相交为"Y"型而不可能为"X"型，因为单链表没有两个next指针。

1、如何判断相交？

判断尾指针，如果尾指针地址相同则相交（注意，不能用尾节点所存储的值是否相同判断，因为之前有可能也有节点存储了和尾节点相同的值）。

2、若相交，如何找出第一个交点？

思路1：A链表的节点依次和B链表的所有节点比较，A的某个节点和B链表的某个节点相等，则这个节点就是交点。

代码如下：

/*** 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* cur1 = headA;ListNode* cur2 = headB;//让A、B链表都走到尾节点while(cur1->next){cur1 = cur1->next;}while(cur2->next){cur2 = cur2->next;}if(cur1 != cur2)//判断尾节点是否相等return NULL;cur1 = headA;while(cur1->next)//让A中每个节点都和B中的所有节点比较{cur2 = headB;while(cur2->next){if(cur1 == cur2)//第一个相等的就是交点return cur2;cur2 = cur2->next;}cur1 = cur1->next;}   return cur2;
}

这个方法的时间复杂度为O(N^2)。

思路2：分别计算出链表A、B的长度，让长的先走差距的步数，然后再让两链表同时开始走，第一个相等的就是交点。

代码如下：

/*** 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* cur1 = headA, * cur2 = headB;int lenA = 0;int lenB = 0;while (cur1->next)//统计链表A的长度{lenA++;cur1 = cur1->next;}while (cur2->next)//统计链表B的长度{lenB++;cur2 = cur2->next;}if (cur1 != cur2)//判断是否有交点return NULL;//假设法，设置长短链表ListNode* LongList = headA, * ShortList = headB;if (lenA < lenB){LongList = headB;ShortList = headA;}int gap = abs(lenA - lenB);//两链表节点差值while (gap--)//让长的先走差值的步数{LongList = LongList->next;}while (LongList != ShortList)//让两链表一起走，第一个相等的就是交点{LongList = LongList->next;ShortList = ShortList->next;}return LongList;
}

这个方法的时间复杂度为O(N)。

对比两种解法，显然第二种方法是更好的。