LeetCode | 面试题 02.04. 分割链表
简单的做法：
- 创建两个带头空链表，大链表和小链表，最后小链表的尾结点和大链表的头结点连接起来
代码如下：
typedef struct ListNode ListNode; struct ListNode* partition(struct ListNode* head, int x){ if(head == NULL) return head; //创建带头的大小链表 ListNode* lessHead,*lessTail; ListNode* greaterHead,*greaterTail; //创建大小链表的哨兵位 lessHead = lessTail = (ListNode*)malloc(sizeof(ListNode)); greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode)); //遍历链表，将节点放到大小链表中 ListNode* cur = head; while(cur) { if(cur->val < x) { //放到小链表中 lessTail->next = cur; lessTail = lessTail->next; } else { //放到大链表中 greaterTail->next = cur; greaterTail = greaterTail->next; } cur = cur->next; } if(greaterTail) greaterTail->next = NULL; //小链表的尾和大链表的头连接起来 lessTail->next = greaterHead->next; //把动态开辟的空间连接起来 free(greaterHead); ListNode* retHead = lessHead->next; free(lessHead); return retHead; }
