题目：给定一个链表和一个数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)。多学一个知识点了。
原文：http://www.cnblogs.com/higerzhang/p/4112528.html
