題目:給定一個鏈表和一個數x,將鏈表中比x小的放在前面,其他的放在后頭。例如:
Given?
1->4->3->2->5->2
?and?
x
?= 3,
return?
1->2->2->4->3->5
.
思路:
1. 再用兩個node,一個指向所有小于x的,一個指向其他的,之后把兩個接在一起。接在一起需要注意large是否未移動過。
/* * * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public : ListNode *partition(ListNode *head, int x) { if (head == NULL || head -> next == NULL) return head; ListNode *ans_small = new ListNode( 0 ); // 存小于x的 ListNode *ans_large = new ListNode( 0 ); // 存不小于x的 ans_small -> next = head; ans_large -> next = head; ListNode *small = ans_small; ListNode *large = ans_large; ListNode *cur = head; while (cur) { if (cur -> val < x) { small -> next = cur; small = cur; cur = cur -> next; } else { large -> next = cur; large = cur; cur = cur -> next; } } large -> next = NULL; // 這個是為了防止large指向head的時候 small -> next = ans_large -> next; head = ans_small; delete ans_small, ans_large; return head -> next; } };
2. 就創建一個node,這個node遇見比x小的就插入

class Solution { public : ListNode *partition(ListNode *head, int x) { if (head == NULL || head -> next == NULL) return head; ListNode *ans = new ListNode( 0 ); ans -> next = head; ListNode *small = ans; // 在它的后面插入小的 ListNode *cur = head; ListNode *pre = ans; // cur的前一個指針,方便插入操作 bool flag = true ; // true說明要插入的緊接著就是下一個,那就不用插入,加加就好 while (cur != NULL) { if (cur -> val < x && small -> next == cur) // 待插入的和之前小的相鄰就不用插入了 { pre = pre -> next; cur = cur -> next; small = small -> next; } else if (cur -> val < x && small -> next != cur) // 不相鄰,插入 { ListNode *tmpnext = small -> next; small -> next = cur; small = cur; cur = cur -> next; small -> next = tmpnext; pre -> next = cur; flag = true ; } else if (cur -> val >= x) { flag = false ; cur = cur -> next; pre = pre -> next; } } head = ans; delete ans; return head -> next; } };
從第二個思路中知道了原來可以判斷連個node是否相等!這個之前以為不能那樣判斷的,原來可以用 if(node1 == node2)。多學一個知識點了。
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
