題目一：移除鏈表元素
OJ
方案一：
題目解析：
代碼演示：
struct ListNode
{
int val;
struct ListNode* next;
};
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* cur = head, * prev = NULL;
while (cur)
{
if (cur->val == val)
{
if (cur == head)
{
head = cur->next;
free(cur);
cur = head;
}
else
{
prev->next = cur->next;
free(cur);
cur = prev->next;
}
}
else
{
prev = cur;
cur = cur->next;
}
}
return head;
}
方案二：
題目解析：把原鏈表遍歷一遍，插入新鏈表
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* newnode = NULL, * tail = NULL;
struct ListNode* cur = head;
while (cur)
{
if (cur->val == val)
{
struct ListNode* del = cur;
cur = cur->next;
free(del);
}
else
{
if (tail == NULL)
{
newnode = tail = cur;
//tail = tail->next;
}
else
{
tail->next = cur;
tail = tail->next;
}
cur = cur->next;
}
}
if (tail)
tail->next = NULL;
return newnode;
}
題目二：反轉(zhuǎn)鏈表
OJ
題目解析：
代碼演示：
struct ListNode
{
int val;
struct ListNode* next;
};
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* newnode = NULL, * cur = head;
while (cur)
{
struct ListNode* next = cur->next;
//尾插
cur->next = newnode;
newnode = cur;
cur = next;
}
return newnode;
}
題目三：鏈表的中間節(jié)點(diǎn)
OJ
題目解析：
代碼演示：
struct ListNode
{
int val;
struct ListNode* next;
};
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* fast = head, * slow = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
題目四：鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)
OJ
題目解析：
代碼演示：
struct ListNode
{
int val;
struct ListNode* next;
};
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
{
struct ListNode* fast = pListHead, * slow = pListHead;
while (k--)
{
if (fast == NULL)
return NULL;
fast = fast->next;
}
while (fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
題目五：合并兩個(gè)有序鏈表
OJ
題目解析：
代碼演示：
struct ListNode
{
int val;
struct ListNode* next;
};
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
if (list1 == NULL)
return list2;
if (list2 = NULL)
return list1;
struct ListNode* tail = NULL, * head = NULL;
head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
while (list1 && list2)
{
if (list1->val < list2->val)
{
tail->next = list1;
tail = tail->next;
list1 = list1->next;
}
else
{
tail->next = list2;
tail = tail->next;
list2 = list2->next;
}
}
if (list1)
tail->next = list1;
if (list2)
tail->next = list2;
struct ListNode* del = head;
head = head->next;
free(del);
return head;
}
題目六：鏈表分割
OJ
題目解析：
代碼演示：
struct ListNode
{
int val;
struct ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
class Partition
{
public:
ListNode* partition(ListNode* pHead, int x)
{
struct ListNode* lhead, * ltail, * gtail, * ghead;
ghead = gtail = (struct ListNode*)malloc(sizeof(struct ListNode));
lhead = ltail = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* cur = pHead;
while (cur)
{
if (cur->val < x)
{
ltail->next = cur;
ltail = ltail->next;
}
else
{
gtail->next = cur;
gtail = gtail->next;
}
cur = cur->next;
}
ltail->next = ghead->next;
gtail->next = NULL;
struct ListNode* head = lhead->next;
free(lhead);
free(ghead);
return head;
}
};
題目七：鏈表的回文結(jié)構(gòu)
OJ
題目解析：
代碼演示：
struct ListNode
{
int val;
struct ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
class PalindromeList
{
public:
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* fast = head, * slow = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* newnode = NULL, * cur = head;
while (cur)
{
struct ListNode* next = cur->next;
cur->next = newnode;
newnode = cur;
cur = next;
}
return newnode;
}
bool chkPalindrome(ListNode* A)
{
struct ListNode* mid = middleNode(A);
struct ListNode* rmid = reverseList(mid);
while (A && rmid)
{
if (A->val != rmid->val)
return false;
A = A->next;
rmid = rmid->next;
}
return true;
}
};
題目八：相交鏈表
OJ
題目解析：
定義快慢指針，使快指針先走與慢指針同步。然后同時(shí)走看是否相交
代碼演示：
struct ListNode
{
int val;
struct ListNode* next;
};
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
struct ListNode* curA = headA, * curB = headB;
int lenA = 1, lenB = 1;
while (curA)
{
curA = curA->next;
lenA++;
}
while (curB)
{
curB = curB->next;
lenB++;
}
if (curA != curB)
return false;
int gab = abs(lenA - lenB);
struct ListNode* longest = headA, * shortest = headB;
if (lenA < lenB)
{
longest = headB;
shortest = headA;
}
while (gab--)
{
longest = longest->next;
}
while (shortest != longest)
{
shortest = shortest->next;
longest = longest->next;
}
return longest;
}
題目九：環(huán)形鏈表
OJ
題目解析：
代碼演示：
struct ListNode {
int val;
struct ListNode* next;
};
bool hasCycle(struct ListNode* head)
{
struct ListNode* fast = head, * slow = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
return true;
}
return false;
}
題目十：環(huán)形鏈表II
OJ
題目解析：
文章來源：http://www.zghlxwxcb.cn/news/detail-753314.html
代碼演示：
struct ListNode
{
int val;
struct ListNode* next;
};
struct ListNode* detectCycle(struct ListNode* head)
{
struct ListNode* fast = head, * slow = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
{
struct ListNode* meet = slow;
while(meet != head)
{
head = head->next;
meet = meet->next;
}
return meet;
}
}
return NULL;
}
??不知不覺，【數(shù)據(jù)結(jié)構(gòu)初階】鏈表OJ以告一段落。通讀全文的你肯定收獲滿滿，讓我們繼續(xù)為數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)共同奮進(jìn)!!!文章來源地址http://www.zghlxwxcb.cn/news/detail-753314.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)初階】鏈表OJ的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
