柚子快報激活碼778899分享：數(shù)據(jù)結構 鏈表OJ題

http://yzkb.51969.com/

今天繼續(xù)分享我們關于鏈表的OJ題。 第一題 合并升序鏈表

這道題我們可以這樣理解，首先是不帶哨兵位，我們先給一個head和tail指針，然后第一個鏈表和第二個鏈表進行比較，如果list1的數(shù)據(jù)比list2的數(shù)據(jù)大的時候，我們就尾插到head中，但是因為我們鏈表沒有哨兵位，所以要考慮是否為空的情況，當我們head不為空的時候，先尾插，然后更新list和tail的位置，往后移動，直到一個鏈表為空的時候，結束，再把不是空的鏈表中的數(shù)據(jù)插入到鏈表當中去。

那我們來寫這道題吧。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){

if(list1==NULL)

{

return list2;

}

if(list2==NULL)

{

return list1;

}

//如果鏈表一個為空，就直接返回不是空的鏈表。

struct ListNode*head;

struct ListNode*tail;

tail=NULL;

head=NULL;

while(list1 && list2)

{

if(list1->val>list2->val)

{

if(head==NULL)

{

head=tail=list2;

//head為空的時候，一個數(shù)據(jù)也沒有

}

else

{

//插入數(shù)據(jù)，更新tail

tail->next=list2;

tail=tail->next;

}

//放入數(shù)據(jù)list要更新

list2=list2->next;

}

else

{

if(tail==NULL)

{

head=tail=list1;

}

else

{

tail->next=list1;

tail=tail->next;

}

list1=list1->next;

}

}

//一個為空的話就退出。然后把不是空的放入就行了。

if(list1==NULL)

{

tail->next=list2;

}

if(list2==NULL)

{

tail->next=list1;

}

return head;

}

上面的代碼是沒有哨兵位的，這題其實有一個哨兵位可能反而簡單一點，讓我們來看看有哨兵位的情況吧。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){

if(list1==NULL)

{

return list2;

}

if(list2==NULL)

{

return list1;

}

struct ListNode*head=( struct ListNode*)malloc(sizeof(struct ListNode));

head->next=NULL;

struct ListNode* tail=head;

while(list1 && list2)

{

if(list1->val>list2->val)

{

tail->next=list2;

tail=tail->next;

list2=list2->next;

}

else

{

tail->next=list1;

tail=tail->next;

list1=list1->next;

}

}

if(list1==NULL)

{

tail->next=list2;

}

if(list2==NULL)

{

tail->next=list1;

}

struct ListNode*next=head->next;

free(head);

return next;

}

代碼明顯簡單一點了，其實也是差不多的，就是有哨兵位不用判斷第一個節(jié)點是否是空，直接放入就行了。

題目二 添加鏈接描述

這道題目我們創(chuàng)建兩個帶哨兵位的鏈表來存放，比它大的放在一個鏈表中，小的在放到另一個鏈表當中，最后進行鏈接就行了。我們來看代碼

class Partition {

public:

ListNode* partition(ListNode* pHead, int x) {

// write code here

struct ListNode*greathead=(struct ListNode*)malloc(sizeof(struct ListNode));

struct ListNode*greattail=greathead;

struct ListNode*lesshead=(struct ListNode*)malloc(sizeof(struct ListNode));

struct ListNode*lesstail=lesshead;

struct ListNode*cur=pHead;

while(cur)

{

if(cur->val>=x)

{

greattail->next=cur;

greattail=greattail->next;

cur=cur->next;

}

else

{

lesstail->next=cur;

lesstail=lesstail->next;

cur=cur->next;

}

}

//防止變成循環(huán)鏈表

greattail->next=NULL;

lesstail->next=greathead->next;

struct ListNode*next=lesshead->next;

free(greathead);

free(lesshead);

return next;

}

};

這道題難在我們?nèi)绾螌㈡湵礞溄?，其實如大家畫畫圖，把大的放一起，小的放一起，這樣最后在鏈接他們就可以解決問題了。

第三題 判斷鏈表是不是回文結構

這道題的思路真的很難想到，我們要先取出中間的位置，然后反轉(zhuǎn)中間位置后面的鏈表，在進行比較，我們先把它當成數(shù)組來理解，就先找到中間數(shù)，然后反轉(zhuǎn)后面的數(shù)，比如圖中的1->2->2->1，經(jīng)過我們上面的步驟就是變成1->2->1->2.然后從中間開始比較過去和第一個比較，如果相等的話就是回文到結束的時候。

/*

struct ListNode {

int val;

struct ListNode *next;

ListNode(int x) : val(x), next(NULL) {}

};*/

struct ListNode* midnode(struct ListNode* head)

{

struct ListNode*slow,*fast;

slow=fast=head;

while(fast && fast->next )

{

slow=slow->next;

fast=fast->next->next;

}

return slow;

}

struct ListNode*midreserve(struct ListNode*mid)

{

struct ListNode*cur=mid;

struct ListNode*prev=NULL;

struct ListNode*head=mid;

struct ListNode*next=mid->next;

while(cur)

{

cur->next=prev;

prev=cur;

cur=next;

if(next)

{

next=next->next;

}

}

return prev;

}

class PalindromeList {

public:

bool chkPalindrome(ListNode* A) {

// write code here

struct ListNode*mid=midnode(A);

struct ListNode*remid=midreserve(mid);

while(remid)

{

if(A->val!=remid->val)

{

return false;

}

A=A->next;

remid=remid->next;

}

return true;

}

};

這道題其實主要是思路難想到，又要先取這個鏈表的中點，然后再去倒置它，在按順序進行比較，真的很難想到，想到了又很難去實現(xiàn)，首先我們先用快慢指針找到中點，然后將中間后面的數(shù)據(jù)進行逆置，可以用頭插的方式，當然也可以用我們?nèi)齻€指針指向前后進行逆置。

做完這個我們再來一題分享題目就算是過去了，原因是后面的題目我也只是會一點，還要繼續(xù)努力。

題目四 相交鏈表

這道題我們先用遍歷一遍headA和headB算出他們的元素個數(shù)，然后找出長的，再找出長的時候我們就可以判斷一個東西，那就是如果最后一個都不相同，那后面就不可能相同，所以結束的時候我們就可以先判斷一下，然后讓長鏈表先走k步，k是他們相差的數(shù)，然后我們就可以一起走，如果不相等就往后，一直到相等的時候，而且這是贏相等的，那我們來看一下代碼吧?。?/p>

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {

struct ListNode *curA=headA;

struct ListNode *curB=headB;

int s1=1;

int s2=1;

while(curA->next)

{

curA=curA->next;

s1++;

}

while(curB->next)

{

curB=curB->next;

s2++;

}

if(curA!=curB)

{

return NULL;

}

int k=abs(s1-s2);

struct ListNode *longNode=headA;

struct ListNode *shortNode=headB;

if(s1

{

longNode=headB;

shortNode=headA;

}

while(k--)

{

longNode=longNode->next;

}

while(longNode!=shortNode)

{

longNode=longNode->next;

shortNode=shortNode->next;

}

return shortNode;

}

今天的分享就到這里了，鏈表的題目后面還有，但是先不分享了等到后面再分享，下一期應該是雙鏈表，這是一個很厲害的鏈表嗷！我們下次見

柚子快報激活碼778899分享：數(shù)據(jù)結構 鏈表OJ題

http://yzkb.51969.com/

相關閱讀