【数据结构】链表OJ题

面试题 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;//根据原节点设置复制节点的randomwhile (cur){struct Node* copy = cur->next;next = copy->next;if (cur->random == NULL){copy->random = NULL;}else{copy->random = cur->random->next;}cur = next;}//将处理好的复制节点链接到newheadcur = 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;
}