目录
- 面试题 02.04 分割链表
- 剑指 Offer II 027 回文链表
- 160 相交链表
- 141 环形链表
- 142 环形链表 II
- 138 复制带随机指针的链表
面试题 02.04 分割链表
- 定义lesshead和greaterhead链接小于和大于等于k的值
- 分别设置哨兵位和尾节点指针
- 最后将两表去除哨兵位再链接
struct ListNode* partition(struct ListNode* head, int x)
{
struct ListNode* lesshead, * lesstail, * greaterhead, * greatertail;
lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));
lesstail->next = NULL;
greaterhead = greatertail = (struct ListNode*)malloc(sizeof(struct ListNode));
greatertail->next = NULL;
struct ListNode* cur = head;
while (cur)
{
if (cur->val < x)
{
lesstail->next = cur;
lesstail = cur;
}
else
{
greatertail->next = cur;
greatertail = cur;
}
cur = cur->next;
}
lesstail->next = greaterhead->next;
greatertail->next = NULL;
struct ListNode* newhead = lesshead->next;
free(lesshead);
free(greaterhead);
return newhead;
}
剑指 Offer II 027 回文链表
- 先找到链表中间节点
- 将中间节点以后的节点从原链表截断逆置生成新链表
- 与原链表逐节点的值相比较
//回文结构
bool isPalindrome(struct ListNode* head) {
if (head == NULL)
{
return false;
}
//找中间节点
struct ListNode* cur = head, * slow = head, * fast = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
struct ListNode* mid = slow;
//将中间节点之后的顺序反转
struct ListNode* newhead = slow;
cur = newhead;
struct ListNode* prev = NULL;
while (cur)
{
struct ListNode* next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
newhead = prev;
//遍历两组链表，检查是否每位相等
struct ListNode* cur2 = newhead;
struct ListNode* cur1 = head;
while (cur1 && cur2)
{
if (cur1->val != cur2->val)
{
return false;
}
cur1 = cur1->next;
cur2 = cur2->next;
}
return true;
}
160 相交链表
- 根据两链表长度求出长度差k
- 较长的链表先走k步
- 两表再一起走，节点地址相同时返回此节点
int ListSize(struct ListNode * head)
{
struct ListNode * cur=head;
int len=0;
while(cur)
{
len++;
cur=cur->next;
}
return len;
}
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
int len1=ListSize(headA);
int len2=ListSize(headB);
int k=abs(len1-len2);
struct ListNode * longlist=headA;
struct ListNode * shortlist=headB;
if(len1<len2)
{
longlist=headB;
shortlist=headA;
}
struct ListNode * cur1=longlist, *cur2=shortlist;
while(k--)
{
cur1=cur1->next;
}
while(cur1 && cur2)
{
if(cur1==cur2)
{
return cur1;
}
cur1=cur1->next;
cur2=cur2->next;
}
return NULL;
}
141 环形链表
快慢指针法，相遇则为环形链表
//环形链表，快慢指针法
bool hasCycle(struct ListNode* head) {
struct ListNode* slow = head;
struct ListNode* fast = head;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if (slow == fast)
{
return true;
}
}
return false;
}
142 环形链表 II
- 先找到入环点
- 相遇点到入环点的距离等于链头到入环点的距离
- 从链头和相遇点出发，相遇点即为入环点
//环形链表 II
//找到入环点，再判断环形链表代码块内续写
struct ListNode* detectCycle(struct ListNode* head) {
struct ListNode* slow = head, * fast = head, * meet = NULL;
while (fast && fast->next)
{
//找到快慢指针相遇点
fast = fast->next->next;
slow = slow->next;
//相遇点到入环点的距离等于链头到入环点的距离
if (slow == fast)
{
meet = slow;
while (meet != head)
{
meet = meet->next;
head = head->next;
}
return meet;
}
}
return NULL;
}
138 复制带随机指针的链表
- 在原链表每个节点后复制一个节点
- 根据原节点设置复制节点的random
- 注意不可复制节点的同时处理random，因为random指向位置还未完成复制
- 将处理好的复制节点链接到newhead
//复制带随机指针的链表
struct Node* copyRandomList(struct Node* head) {
struct Node* cur = head;
//在原链表每个节点后复制一个节点
while (cur)
{
struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
copy->val = cur->val;
copy->next = cur->next;
cur->next = copy;
cur = copy->next;
}
cur = head;
struct Node* next = NULL;
//根据原节点设置复制节点的random
while (cur)
{
struct Node* copy = cur->next;
next = copy->next;
if (cur->random == NULL)
{
copy->random = NULL;
}
else
{
copy->random = cur->random->next;
}
cur = next;
}
//将处理好的复制节点链接到newhead
cur = head;
struct Node* newtail = NULL, * newhead = NULL;
while (cur)
{
struct Node* copy = cur->next;
next = copy->next;
if (newtail == NULL)
{
newhead = newtail = copy;
}
else
{
newtail->next = copy;
newtail = copy;
}
cur->next = next;
cur = next;
}
return newhead;
}
