前言
新的一年，好好学习。
正文
问题来源
本问题来自leetcode上的86题。
问题描述
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例 1：
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
分析：
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func partition(head *ListNode, x int) *ListNode {
if head == nil {
return nil
}
newHead := &ListNode{0, head}
q := newHead
for (q.Next != nil)&&(q.Next.Val < x) {
fmt.Println(q.Next.Val)
q = q.Next
}
p := q.Next
for ;p != nil && p.Next != nil; {
if p.Next.Val < x {
temp := p.Next
p.Next = p.Next.Next
temp.Next = q.Next
q.Next = temp
q = q.Next
//fmt.Println(p.Next.Val)
continue
}
p = p.Next
}
return newHead.Next
}
感觉自己写的不是很好，找到了一个不错的代码
/**
* 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) {
ListNode less_head(0); //设置两个临时的头节点
ListNode more_head(0);
ListNode *less_ptr = &less_head; //对应指针指向两个头节点
ListNode *more_ptr = &more_head;
while(head){
if(head->val < x){ //如果节点值小于x，则将节点插入less_ptr后
less_ptr->next = head;
less_ptr = head;
}
else{ //否则将节点插入more_ptr后
more_ptr->next = head;
more_ptr = head;
}
head = head->next; //遍历链表
}
less_ptr->next = more_head.next;
more_ptr->next = NULL; //将more_ptr即链表尾节点next置空
return less_head.next; //less_head的next节点即为新链表头节点，返回
}
};
总结：
勤思考。
结语
不管怎么样好好加油。
