链表的基础oj

单链表基础题

OR36 链表的回文结构

https://www.nowcoder.com/ta/2016test?tag=581

对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。

给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。

思路:已知长度小于等于900,那么逆置半个链表也可以看做O(1)

1.先找到中间结点,有两个就返回第二个

2.逆置midnode链表

class PalindromeList {
public:
 struct ListNode* middleNode(struct ListNode* head)
 {
 int count = 0;
 struct ListNode* t = head;
 while(t!= NULL)
 {
 ++count;
 t = t->next;
 }
 
 int count1 = count/2;
 t = head;
 while(count1--)
 {
 t = t->next;
 }
 
 return t;
 }
struct ListNode* reverseList(struct ListNode* head)
{
 struct ListNode* t = head;
 int a[910] = {0};
 int count = 0;
 while(t != NULL)
 {
 a[count++] = t->val;
 t = t->next;
 }
 struct ListNode* h = ( struct ListNode*)malloc(sizeof( struct ListNode));
 struct ListNode* coph = h;
 coph->next = NULL;
 for(int i=count-1;i>=0;--i)
 {
 struct ListNode* newnode = ( struct ListNode*)malloc(sizeof( struct ListNode));
 newnode->next = NULL;
 newnode->val = a[i];
 h ->next = newnode;
 h = newnode;
 }
 return coph->next;
}
 bool chkPalindrome(ListNode* A) 
 {
 // write code here
 struct ListNode* midnode = middleNode(A);
 struct ListNode* rhead = reverseList(midnode);
 
 struct ListNode* t1 = A;
 struct ListNode* t2 = rhead;
 while(t2 != NULL)
 {
 if(t1->val != t2->val)
 return false;
 t1 = t1->next;
 t2 = t2->next;
 }
 return true;
 }
};

141. 环形链表

https://leetcode.cn/problems/linked-list-cycle/description/

给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

思路:先考虑有没有环,没环链表遍历一定会结束

如果有环,链表两个速度不一样的指针会在环里面追击,若相差速度为1则一定可以相遇

bool hasCycle(struct ListNode *head) {
 struct ListNode * slow = head;
 struct ListNode * fast = head;
 
 while(fast!= NULL && fast->next != NULL)
 {
 slow = slow->next;
 fast = fast->next->next;
 
 if(slow == fast)
 return true;
 }
 return false;
}

142. 环形链表 II

https://leetcode.cn/problems/linked-list-cycle-ii/

给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos-1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

不允许修改 链表。

思路:假设在有环的链表中,slow与fast在meet处相遇,设链表头结点到环的第一个结点共L,环的第一个结点到meet共x,整个环共c个结点。

可以看出,slow必定在第一圈和fast相遇。因为它们的距离一定小于一圈,就算slow走了一圈,fast就走了两圈,他们之间又差一圈,它们的速度差是1,fast在每一步之之后它们的相差距离都减少了1。

在第一次相遇时:

slow走了 l+x

fast走了l+nc+x == 2(l+x)

解得l = (n-1)c + c - x,也就是说:meet到环第一个结点的步数等于Head到环第一个结点的步数

 struct ListNode * hasCycle(struct ListNode *head) 
 {
 struct ListNode * slow = head;
 struct ListNode * fast = head;
 while(fast!= NULL && fast->next != NULL)
 {
 slow = slow->next;
 fast = fast->next->next;
 if(slow == fast)
 return slow;
 }
 return NULL;
}
ListNode *detectCycle(ListNode *head) 
{
 struct ListNode *meet = hasCycle(head);
 if(meet == NULL)return NULL;
 struct ListNode *t1 = head;
 struct ListNode *t2 = meet;
 while(t1 != t2)
 {
 t1 = t1->next;
 t2 = t2->next;
 }
 return t1;
}
作者:月亮给蒙娜丽莎原文地址:https://segmentfault.com/a/1190000043794056

%s 个评论

要回复文章请先登录注册