题一:链表分割
现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。
思路一:
1.分别创建一个记录小于x的“小”结构体,和记录大于等于x的“大”结构体,
2.然后malloc函数动态开辟一个结构体大小的空间,这时head和tail都指向同一位置,将phead->val与x比较,小于想,放入less中,大于等于x放入great中,
3.当phead为NULL时,将两个“大”“小”结构体链接起来,记录lesshead节点,然后free释放开辟的动态内存空间,返回记录lesshead的地址。
ListNode* partition(ListNode* phead, int x) { struct ListNode* head = phead ; struct ListNode* lesshead ; struct ListNode* greathead ; struct ListNode* lesstail ; struct ListNode* greattail ; //动态开辟空间 lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode)); greathead = greattail = (struct ListNode*)malloc(sizeof(struct ListNode)); while(head) { //小于x的尾插到lessTail if(head->val < x) { lesstail->next = head; lesstail = lesstail->next; } //大于等于x的尾插到greaterTail else { greattail->next = head; greattail = greattail->next; } //下一个位置 head = head->next; } //小的接上大的 lesstail->next = greathead->next; greattail->next = NULL; //新头节点 struct ListNode* Phead = lesshead->next; //销毁 free(lesshead); free(greathead); return Phead; }
题二:相交链表
给你两个单链表的头节点 headA
和 headB
,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null
。
图示两个链表在节点 c1
开始相交:
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
思路一:
1.先分别将A和B遍历一遍,计算出长度len
2.计算长度差Slen,让长的先指向Slen个next位置
3.此时再同时遍历,直到A和B的地址相同,
4.返回的就是第一个交点
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode* curA = headA,*curB = headB; int len1 = 1,len2 = 1; //计算链表长度 while(curA) { curA = curA->next; len1++; } while(curB) { curB = curB->next; len2++; } //如果此时遍历结束地址不相等,说明没有相交点 if(curA != curB) { return NULL; } //abs是计算差值绝对值函数 int Slen = abs(len1 - len2); //二次遍历的长短链表 struct ListNode* longlist = headA,*shortlist = headB; if(len1 < len2) { longlist = headB; shortlist = headA; } //让longlist和shortlist的长度相同 while(Slen--) { longlist = longlist->next; } //找到第一个交点 while(longlist != shortlist) { longlist = longlist->next; shortlist = shortlist->next; } //输出交点地址 return longlist; }
题三:环形链表
给你一个链表的头节点 head
,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next
指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos
来表示链表尾连接到链表中的位置(索引从 0 开始)。注意:pos
不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ,则返回 true
。 否则,返回 false
。
示例 1:
思路一:
快慢指针思路:
1.创建快慢指针fast和slow;
2.开始位置相同,slow每次指向下一个地址, fast每次指向下下个地址;
3.循环判断,直到slow=fast地址相同;
4,相同则说明链表存在环;
反之,fast或fast->next尾NULL则不存在环。
bool hasCycle(struct ListNode *head) { struct ListNode* slow = head; struct ListNode* fast = head; //fast或fast->next尾NULL则不存在环 while(fast && fast->next) { //slow每次指向下一个地址, fast每次指向下下个地址 slow = slow->next; fast = fast->next->next; //相同则说明链表存在环 if(slow == fast) { return true; } } return false; }
题四:链表的回文结构
思路一:
如下:两种方法,得到的节点去循环判断,如果newnode或者head一个为NULL,则说明是回文结构,如果在循环中结束·,则不是回文结构。
链表反转:
三个变量n1=NULL,n2=head,n3,如果n2不为NULL,则n3=n2->next,循环如果n2为NULL,就停下来,当n3为空时n3就不进行变化,最后n1会停在最后一个位置,这个时候逆置完成。
查找中间节点:
分别定义快慢两个指针,快指针一次前进两个地址,慢指针一次前进一个地址,当奇数时快指针的next为NULL时,当链表为偶数时判断条件为地址为NULL,停下来,此时慢指针就在链表中间节点上。
//将链表反转 struct ListNode* reverseList(struct ListNode* head) { struct ListNode* n1,*n2,*n3; n1 = NULL; n2 = head; if(n2) n3 = n2->next; while(n2) { n2->next = n1; n1 = n2; n2 = n3; if(n3) n3 = n3->next; } return n1; } //得到链表中间节点 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; } class PalindromeList { public: bool chkPalindrome(ListNode* head) { struct ListNode* mid = middleNode(head); struct ListNode* newnode = reverseList(mid); //一个为空自己退出 while(newnode && head) { //不相同,则不是回文结构 if(newnode->val != head->val) { return false; } newnode = newnode->next; head = head->next; } return true; } };