欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode 86 分隔链表 / partition list

程序员文章站 2022-05-12 09:17:26
...

题目描述:

leetcode 86 分隔链表 / partition list

    又是关于链表的操作题,感觉自己做这类题比较缺乏经验,想到哪写到哪,代码原没有别人简洁明了,还需要多多学习。

参考代码:

/**
 * 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 dummy1(-1),dummy2(-1);
        ListNode *root1=&dummy1,*root2=&dummy2;
        while(head){
            if(head->val<x){
                root1->next=head;
                head=head->next;
                root1=root1->next;
                root1->next=NULL;
            }
            else{
                root2->next=head;
                head=head->next;
                root2=root2->next;
                root2->next=NULL;
            }
        }
        root1->next=dummy2.next;
        return dummy1.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) {
		if(head == NULL) return head;
		ListNode* q = head;
		ListNode* temp;
		int total = 1;
		while(q -> next != NULL){
			total += 1;
			q = q -> next;
		} // q记录最后一个节点
		ListNode* p = head;
		int cnt = 0;
		while(p -> val >= x && cnt < total){ // 找到第一个小于x的节点
			temp = p;
			q -> next = temp;
			p = p -> next;
			temp -> next = NULL;
			q = temp;
			cnt += 1;
		}
		if(cnt > total) return p;
		cnt += 1;
		if(cnt == total) return p;
		ListNode* begin = p;
		while(cnt < total){
			if(p -> next != NULL && p -> next -> val < x){
				p = p -> next;
				cnt += 1;
			}
			else if(p -> next != NULL && p -> next -> val >= x){
				temp = p -> next;
				q -> next = temp;
				p -> next = p -> next -> next;
				temp -> next = NULL;
				q = temp;
				cnt += 1;
			}
		}
		return begin;
    }
};