柚子快報(bào)激活碼778899分享：數(shù)據(jù)結(jié)構(gòu) 鏈表OJ題
柚子快報(bào)激活碼778899分享：數(shù)據(jù)結(jié)構(gòu) 鏈表OJ題
今天繼續(xù)分享我們關(guān)于鏈表的OJ題。 第一題 合并升序鏈表
這道題我們可以這樣理解，首先是不帶哨兵位，我們先給一個(gè)head和tail指針，然后第一個(gè)鏈表和第二個(gè)鏈表進(jìn)行比較，如果list1的數(shù)據(jù)比list2的數(shù)據(jù)大的時(shí)候，我們就尾插到head中，但是因?yàn)槲覀冩湵頉]有哨兵位，所以要考慮是否為空的情況，當(dāng)我們head不為空的時(shí)候，先尾插，然后更新list和tail的位置，往后移動(dòng)，直到一個(gè)鏈表為空的時(shí)候，結(jié)束，再把不是空的鏈表中的數(shù)據(jù)插入到鏈表當(dāng)中去。
那我們來寫這道題吧。
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
if(list1==NULL)
{
return list2;
}
if(list2==NULL)
{
return list1;
}
//如果鏈表一個(gè)為空，就直接返回不是空的鏈表。
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í)候，一個(gè)數(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;
}
}
//一個(gè)為空的話就退出。然后把不是空的放入就行了。
if(list1==NULL)
{
tail->next=list2;
}
if(list2==NULL)
{
tail->next=list1;
}
return head;
}
上面的代碼是沒有哨兵位的，這題其實(shí)有一個(gè)哨兵位可能反而簡單一點(diǎn)，讓我們來看看有哨兵位的情況吧。
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;
}
代碼明顯簡單一點(diǎn)了，其實(shí)也是差不多的，就是有哨兵位不用判斷第一個(gè)節(jié)點(diǎn)是否是空，直接放入就行了。
題目二 添加鏈接描述
這道題目我們創(chuàng)建兩個(gè)帶哨兵位的鏈表來存放，比它大的放在一個(gè)鏈表中，小的在放到另一個(gè)鏈表當(dāng)中，最后進(jìn)行鏈接就行了。我們來看代碼
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)绾螌㈡湵礞溄?，其?shí)如大家畫畫圖，把大的放一起，小的放一起，這樣最后在鏈接他們就可以解決問題了。
第三題 判斷鏈表是不是回文結(jié)構(gòu)
這道題的思路真的很難想到，我們要先取出中間的位置，然后反轉(zhuǎn)中間位置后面的鏈表，在進(jìn)行比較，我們先把它當(dāng)成數(shù)組來理解，就先找到中間數(shù)，然后反轉(zhuǎn)后面的數(shù)，比如圖中的1->2->2->1，經(jīng)過我們上面的步驟就是變成1->2->1->2.然后從中間開始比較過去和第一個(gè)比較，如果相等的話就是回文到結(jié)束的時(shí)候。
/*
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;
}
};
這道題其實(shí)主要是思路難想到，又要先取這個(gè)鏈表的中點(diǎn)，然后再去倒置它，在按順序進(jìn)行比較，真的很難想到，想到了又很難去實(shí)現(xiàn)，首先我們先用快慢指針找到中點(diǎn)，然后將中間后面的數(shù)據(jù)進(jìn)行逆置，可以用頭插的方式，當(dāng)然也可以用我們?nèi)齻€(gè)指針指向前后進(jìn)行逆置。
做完這個(gè)我們?cè)賮硪活}分享題目就算是過去了，原因是后面的題目我也只是會(huì)一點(diǎn)，還要繼續(xù)努力。
題目四 相交鏈表
這道題我們先用遍歷一遍headA和headB算出他們的元素個(gè)數(shù)，然后找出長的，再找出長的時(shí)候我們就可以判斷一個(gè)東西，那就是如果最后一個(gè)都不相同，那后面就不可能相同，所以結(jié)束的時(shí)候我們就可以先判斷一下，然后讓長鏈表先走k步，k是他們相差的數(shù)，然后我們就可以一起走，如果不相等就往后，一直到相等的時(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; } 今天的分享就到這里了，鏈表的題目后面還有，但是先不分享了等到后面再分享，下一期應(yīng)該是雙鏈表，這是一個(gè)很厲害的鏈表嗷！我們下次見 柚子快報(bào)激活碼778899分享：數(shù)據(jù)結(jié)構(gòu) 鏈表OJ題 相關(guān)閱讀
本文內(nèi)容根據(jù)網(wǎng)絡(luò)資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點(diǎn)和立場(chǎng)。
轉(zhuǎn)載請(qǐng)注明，如有侵權(quán)，聯(lián)系刪除。
Netshoes鞋履購物坊
