数据结构OJ题链表分割

原题链接：https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

目录

1. 题目描述

2. 思路分析

3. 代码实现

1. 题目描述

2. 思路分析

整体思路：创建两个链表，分别存放小于x的结点和大于等于x的结点，分别进行尾插。

这道题目使用哨兵位会更简单，原因如下（能避开很多为空的情况）：

（1）使用哨兵位就不需要考虑两个链表尾插时为空的情况。

（2）两个链表链接时也不需要考虑是否为空的情况。

（3）哪怕有一个链表为空，也有哨兵位的头结点，正常链接即可。

我们用结构体指针lhead和ltail分别表示值小于x的那一条链表，用结构体指针ghead和gtail表示值大于等于x的那一条链表。

用malloc()函数分别申请两个结点，也就是两个链表的哨兵位，让lhead和ltail一开始指向其中一个，ghead和gtail一开始指向另一个。

再创建一个结构体指针cur用来遍历原链表，我们采用了while循环，当cur不为空时遍历结点。

当结点的值小于x时，我们将这个结点尾插到第一个链表（ltail->next=cur）。再让ltai往后走一步（ltai=ltail->next）。

当结点的值大于等于x时，我们将结点尾插到第二个链表（gtail->next=cur）。再让gtail往后走一 一步（gtail=gtail->next）。

尾插一个结点后，让cur往后走一步（cur=cur->next）。当cur为空时停止循环。

然后将两个链表链接起来。（ltail->next=ghead->next）。

有一点需要非常注意！！！

将gtail->next=NULL

否则可能会出现环。

因为现在lhead指向的是哨兵位，所以我们要将lhead往后走一步（lhead=lhead->next）。

因为怕找不到lhead的下一个位置，所以我们引入一个结构体指针head保存lhead的下一个位置。（struct ListNode *head=lhead->next）。

然后为了防止内存泄漏，我们要用free()释放掉两个哨兵位（即free(lhed)和free(ghead)）。

最后返回head即可。

3. 代码实现

1.  
   /*
2.  
   struct ListNode {
3.  
   int val;
4.  
   struct ListNode *next;
5.  
   ListNode(int x) : val(x), next(NULL) {}
6.  
   };*/
7.  
   class Partition {
8.  
   public:
9.  
   ListNode* partition(ListNode* pHead, int x) {
10.  
    struct ListNode *lhead,*ltail,*ghead,*gtail;
11.  
    lhead=ltail=(struct ListNode*)malloc(sizeof(struct ListNode));
12.  
    ghead=gtail=(struct ListNode*)malloc(sizeof(struct ListNode));
13.  
    struct ListNode *cur=pHead;
14.  
    while(cur)
15.  
    {
16.  
    if(cur->val<x)
17.  
    {
18.  
    ltail->next=cur;
19.  
    ltail=ltail->next;
20.  
    }
21.  
    else
22.  
    {
23.  
    gtail->next=cur;
24.  
    gtail=gtail->next;
25.  
    }
26.  
    cur=cur->next;
27.  
    }
28.  
    ltail->next=ghead->next;
29.  
    //不空，可能导致出现环
30.  
    gtail->next=NULL;
31.  
    struct ListNode *head=lhead->next;
32.  
    free(lhead);
33.  
    free(ghead);
34.  
    return head;
35.  
    }
36.  
    };

这篇好文章是转载于：学新通技术网