Day3-线性表-链表划分，保持相对位置

BUPTrenyi

发布于 2019-07-16 11:38:18

4030

发布于 2019-07-16 11:38:18

文章被收录于专栏：算法其实很好玩算法其实很好玩

一今天不废话，直接上题

今天吃饭晚了点，导致盒饭迟到了一会。

而吃饭晚的原因又是什么呢？因为今天开周会，大家聊得比较嗨。

那么大家到底聊了什么呢这么嗨？因为在复盘这周的一次线上事故，大家畅所欲言就聊嗨了。

那等下第二篇盒饭会讲这次复盘吗？当然会讲啦~

哎等下，你不是说不废话吗？

二题目

Q：已知链表头指针及数X，将所有小于X的节点，放在大于等于X的节点前，且保持这些节点的原来的相对位置

那么问题来了，保持相对位置是什么意思？

答曰：如【1。。。2】最后的链表，1也要在2的左边，这叫保持相对位置

那么，冷静分析：

伟大的哲学家鲁迅曾经说过，链表问题，快慢指针，临时头节点，以及关键节点，就这仨思路

那么对于链表

1->4->3->2->5->2

来说，最终结果就应该是(保持相对位置)

1->2->2->4->3->5

那么，我建两个临时头节点，在遍历原链表的过程中

比X小的，插在小的临时头节点后面

比X大的，插在大的临时头节点后面

那么就是：

less_head->1->2->2

more_head->4->3->5

那么此时我只要完成2->more_head

两个链表不就连上了，就是最终结果了嘛

三完整代码及注释

//
// Created by renyi on 2019/5/31.
//
#include <iostream>
using namespace std;

struct Node{
    int value;
    Node* next;
    Node(int v):value(v),next(NULL){}
};

Node* separateList(Node* head, int x){
    Node less_head(0);//创建两个临时头节点
    Node more_head(0);

    Node* less = &less_head;//对应指针指向这两个临时头节点
    Node* more = &more_head;

    while(head){
        if (head->value < x){//若节点值小于x，应插到less_head后面
            less->next = head;
            less = head;//链接完节点以后，应该将less后移，指向head
        } else{
            more->next = head;//若节点值大于x，应插到more_head后面
            more = head;//链接完节点以后，应该将less后移，指向head
        }
        head = head->next;
    }
    less->next = more_head.next;//此时less指针的后继应指向，more_head头节点的后继，即more_head部分第一个节点
    more->next = NULL;//此时more指针遍历到链表尾，后继置空
    return less_head.next;
}

void print(Node* head){//对比第一天的print函数，改进了一下
    while(head){
        if (head->next){
            cout<<head->value<<"->";
        } else{
            cout<<head->value;
        }
        head = head->next;
    }
    cout<<endl;
}

int main(){
    Node a(1);
    Node b(6);
    Node c(2);
    Node d(7);
    Node e(10);
    Node f(3);
    Node g(4);
    Node h(9);
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;
    e.next = &f;
    f.next = &g;
    g.next = &h;

    Node* head = separateList(&a, 5);
    print(head);
    return 0;
}

最终结果就是