一、链表分割
题目链接:NowCoder
题目要求将链表分割,值小于 x 的节点放在左边,大于等于 x 的节点放在右边。
解题思路: 创建两个新链表(小链表和大链表),使用哨兵位节点占位以避免空链表判断。遍历原链表,将节点分别接入对应链表,最后连接小链表尾与大链表头,并释放哨兵节点。
ListNode* partition(ListNode* pHead, int x) {
ListNode* lesshead = NULL, *lesstail = NULL;
ListNode* greaterhead = NULL, *greatertail = NULL;
// 初始化哨兵节点
lesshead = lesstail = (ListNode*)malloc(sizeof(ListNode));
greaterhead = greatertail = (ListNode*)malloc(sizeof(ListNode));
ListNode* pcur = pHead;
while(pcur) {
if(pcur->val < x) {
lesstail->next = pcur;
lesstail = pcur;
} else {
greatertail->next = pcur;
greatertail = pcur;
}
pcur = pcur->next;
}
// 连接大小链表
lesstail->next = greaterhead->next;
// 断开大链表尾部防止成环
greatertail->next = NULL;
// 获取结果头结点
ListNode* ret = lesshead->next;
// 释放哨兵节点
free(lesshead);
free(greaterhead);
return ret;
}
二、相交链表
题目链接:LeetCode
题目要求判断两个链表是否相交,若相交返回相交节点,否则返回空。
解题思路: 由于两链表长度可能不同,直接遍历无法保证同时到达相交点。先计算两链表长度,让长链表先走长度差步数,使两指针处于同一起跑线,然后同步遍历。若相遇则返回该节点,否则返回 NULL。
struct ListNode* getIntersectionNode( ListNode* headA, ListNode* headB) {
* pcurA = headA;
* pcurB = headB;
countA = , countB = ;
(pcurA) { countA++; pcurA = pcurA->next; }
(pcurB) { countB++; pcurB = pcurB->next; }
* lesslist = headA;
* greaterlist = headB;
(countA > countB) {
lesslist = headB;
greaterlist = headA;
}
size = (countA - countB);
(size--) {
greaterlist = greaterlist->next;
}
(lesslist) {
(lesslist == greaterlist) lesslist;
lesslist = lesslist->next;
greaterlist = greaterlist->next;
}
;
}


