链表分割 牛客网 程序员面试金典 C++ Python

链表分割 牛客网 程序员面试金典 C++ Python

题目描述编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前给定一个链表的头指针 ListNode* pHead，请返回重新排列后的链表的头指针。注意：分割以后保持原来的数据顺序不变。

c++

/* * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * };*/ class Partition { public: //run:4ms memory:480k ListNode* partition(ListNode* pHead, int x){ if(pHead==NULL) return NULL; ListNode *pNode = pHead; ListNode *small = new ListNode(0); ListNode *big = new ListNode(0); ListNode *pSmall = small; ListNode *pBig = big; while(pNode){ if(pNode->val<x){ pSmall->next = pNode; pNode = pNode->next; pSmall = pSmall->next; pSmall->next = NULL; }else{ pBig->next = pNode; pNode = pNode->next; pBig = pBig->next; pBig->next = NULL; } } pSmall->next = big->next; free(big); pNode = small->next; free(small); return pNode; } };

Python

# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Partition: #run:94ms memeory:5688k def partition(self, pHead, x): if None == pHead: return None pNode = pHead small = ListNode(0) big = ListNode(0) pSmall = small pBig = big while pNode: if pNode.val < x: pSmall.next = pNode pNode = pNode.next pSmall = pSmall.next pSmall.next = None else: pBig.next = pNode pNode = pNode.next pBig = pBig.next pBig.next = None pSmall.next = big.next return small.next

 

转载于:https://www.cnblogs.com/vercont/p/10210299.html

相关资源：JAVA上百实例源码以及开源项目