首页 > 试题广场 >

将单向链表按某值划分为左边小,中间相等,右边大的形式

[编程题]将单向链表按某值划分为左边小,中间相等,右边大的形式
  • 热度指数:4522 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个链表,再给定一个整数 pivot,请将链表调整为左部分都是值小于 pivot 的节点,中间部分都是值等于 pivot 的节点, 右边部分都是大于 pivot 的节点。
除此之外,对调整后的节点顺序没有更多要求。

输入描述:
第一行两个整数 n 和 pivot,n 表示链表的长度。

第二行 n 个整数 ai 表示链表的节点。


输出描述:
请在给定的函数内返回链表的头指针。
示例1

输入

5 3
9 0 4 5 1

输出

1 0 4 5 9

备注:

list_node * list_partition(list_node * head, int pivot)
{
    //////在下面完成代码
    list_node *smallHead = NULL, *smallTail = NULL;
    list_node *equalHead = NULL, *equalTail = NULL;
    list_node *bigHead = NULL, *bigTail = NULL;
    while (head) {
        if (head->val < pivot) {
            if (smallHead == NULL) {
                smallHead = head;
                smallTail = head;
            } else {
                smallTail->next = head;
                smallTail = head;
            }
        } else if (head->val == pivot) {
            if (equalHead == NULL) {
                equalHead = head;
                equalTail = head;
            } else {
                equalTail->next = head;
                equalTail = head;
            }
        } else {
            if (bigHead == NULL) {
                bigHead = head;
                bigTail = head;
            } else {
                bigTail->next = head;
                bigTail = head;
            }
        }
        head = head->next;
    }
    if (smallTail) smallTail->next = NULL;
    if (equalTail) equalTail->next = NULL;
    if (bigTail) bigTail->next = NULL;
    list_node *res;
    if (smallHead == NULL && equalHead == NULL && bigHead == NULL) res = NULL;
    else if (smallHead == NULL && equalHead == NULL) res = bigHead;
    else if (smallHead == NULL && bigHead == NULL) res = equalHead;
    else if (equalHead == NULL && bigHead == NULL) res = smallHead;
    else if (smallHead == NULL) {
        equalTail->next = bigHead;
        res = equalHead;
    } else if (equalTail == NULL) {
        smallTail->next = bigHead;
        res = smallHead;
    } else if (bigTail == NULL) {
        smallTail->next = equalHead;
        res = smallHead;
    } else {
        smallTail->next = equalHead;
        equalTail->next = bigHead;
        res = smallHead;
    }
    head = res;
    while (head) {
        printf("%d ", head->val);
        head = head->next;
    }
    return res;

发表于 2021-09-14 20:49:28 回复(0)
python3代码 感觉最精简好理解的了
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def partition(self, head, pivot):
        sh, st = None, None  # 小于部分头尾
        eh, et = None, None  # 等于部分头尾
        bh, bt = None, None  # 大于部分头尾
        while head:
            sign = head
            head = head.next  # 保留下一节点
            sign.next = None  # 剥离出当前节点 不然可能会出现循环链表
            if sign.val < pivot:
                if not sh:
                    sh = sign
                    st = sign
                else:
                    st.next = sign
                    st = sign
            elif sign.val == pivot:
                if not eh:
                    eh = sign
                    et = sign
                else:
                    et.next = sign
                    et = sign
            else:
                if not bh:
                    bh = sign
                    bt = sign
                else:
                    bt.next = sign
                    bt = sign

        if st:  # 有小于部分
            head = sh
            if eh:  # 且有等于部分
                st.next = eh
                if bh:
                    et.next = bh
            elif bh:  # 且无等于部分但有大于部分
                st.next = bh
        elif et:  # 无小于部分但有等于部分
            head = head if head else eh
            if bh:
                et.next = bh
        return head if head else bh  # 无小于部分也无等于部分


编辑于 2020-01-12 16:24:50 回复(0)
在遍历原始链表的过程中构建3个链表,分别为小于、等于和大于链表。最后再将三个链表按小于、等于、大于的顺序连接起来。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().trim().split(" ");
        int n = Integer.parseInt(params[0]);
        int pivot = Integer.parseInt(params[1]);
        String[] strList = br.readLine().trim().split(" ");
        ListNode head = new ListNode(Integer.parseInt(strList[0]));
        ListNode cur = head;
        for(int i = 1; i < n; i++){
            cur.next = new ListNode(Integer.parseInt(strList[i]));
            cur = cur.next;
        }
        head = partition(head, pivot);
        while(head != null){
            System.out.print(head.val + " ");
            head = head.next;
        }
    }
    
    private static ListNode partition(ListNode node, int target) {
        ListNode less = new ListNode(-1);
        ListNode equal = new ListNode(-1);
        ListNode great = new ListNode(-1);
        ListNode head1 = less;
        ListNode head2 = equal;
        ListNode head3 = great;
        while(node != null){
            if(node.val < target){
                less.next = new ListNode(node.val);
                less = less.next;
            }else if(node.val > target){
                great.next = new ListNode(node.val);
                great = great.next;
            }else{
                equal.next = new ListNode(node.val);
                equal = equal.next;
            }
            node = node.next;
        }
        if(head3.next != null){
            equal.next = head3.next;
            head3.next = null;       // 把大于链表头部的哑节点断开
        }
        if(head2.next != null){
            less.next = head2.next;
            head2.next = null;       // 把等于链表头部的哑节点断开
        }
        return head1.next;
    }
}

发表于 2021-06-11 14:08:41 回复(0)
题目:给定一个链表,再给定一个整数 pivot,请将链表调整为左部分都是值小于 pivot 的节点,中间部分都是值等于 pivot 的节点, 右边部分都是大于 pivot 的节点。
除此之外,对调整后的节点顺序没有更多要求。

疑问:不是说对调整后的节点顺序没有更多要求吗,测试用例是
5 3
9 0 4 5 1
答案是 1 0 4 5 9
我的是 0 1 9 4 5
为什么不通过,确实是小于在左啊,等于没有,然后大于在右边的。代码如下:
import java.io.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {

    static class ListNode{
        int val;
        ListNode next;
        public ListNode() {};
        public ListNode(int val) {
            this.val = val;
        }
    }

    private static StreamTokenizer st;
    private static PrintWriter pw;

    static {
        st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    }

    public static void main(String[] args) {
        int n = init(st);
        int pivot = init(st);
        ListNode head = initialize(n);
        ListNode sStart = null,sEnd = null,
        mStart = null,mEnd = null,bStart = null,bEnd = null;
        ListNode cur = head;
        while(cur != null) {
            if(cur.val < pivot) {
                if(sEnd == null) {
                    sStart = cur;
                    sEnd = cur;
                }else {
                    sEnd.next = cur;
                    sEnd = cur;
                }
            }else if(cur.val == pivot) {
                if(mEnd == null) {
                    mStart = cur;
                    mEnd = cur;
                }else {
                    mEnd.next = cur;
                    mEnd = cur;
                }
            }else {
                if(bEnd == null) {
                    bStart = cur;
                    bEnd = cur;
                }else {
                    bEnd.next = cur;
                    bEnd = cur;
                }
            }
            cur = cur.next;
        }
        bEnd.next = null;
        if(sEnd != null) {
            sEnd.next = mEnd == null ? bStart : mStart;
        }
        if(mEnd != null) {
            mEnd.next = bStart;
        }
        head = sStart == null ? mStart == null ? bStart : mStart : sStart;
        cur = head;
        while(cur != null) {
            pw.print(cur.val + " ");
            pw.flush();
            cur = cur.next;
        }
    }
    private static ListNode initialize(int n) {
        int[] vals = new int[n];
        for(int i = 0;i < n;i++)
            vals[i] = init(st);
        ListNode head = new ListNode(vals[0]);
        ListNode cur = head;
        for(int i = 1;i < n;i++) {
            cur.next = new ListNode(vals[i]);
            cur = cur.next;
        }
        return head;
    }
    private static int init(StreamTokenizer st) {
        try {
            st.nextToken();
        }catch(IOException e) {
            e.printStackTrace();
        }
        return (int)st.nval;
    }
}

发表于 2023-07-17 15:21:34 回复(1)
这个咋就只能过90%,不知道后台怎么判断结果的???

``` java
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int pivot = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        Node head = genLinkedListByHead(arr);
        head = partitionOfLinkedList(head, pivot);
        printLinkedList(head);
    }
    
    private static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }
    
    public static Node genLinkedListByHead(int[] arr) {
        if (arr == null || arr.length < 1) {
            return null;
        }

        Node next = null, node;
        for (int i = arr.length - 1; i >= 0; i--) {
            node = new Node(arr[i]);
            node.next = next;
            next = node;
        }

        return next;
    }
    
    public static void printLinkedList(Node head) {
        StringBuilder sb = new StringBuilder();
        while (head != null) {
            sb.append(head.val).append(" ");
            head = head.next;
        }
        System.out.println(sb.toString());
    }
    
    public static Node partitionOfLinkedList(Node head, int pivot) {
        Node tou = new Node(0);
        Node lt = tou, eq = null, gt = null, nxt, t;

        // 头插法
        while (head != null) {
            nxt = head.next;
            head.next = null;
            if (head.val < pivot) { // 在 lt 与 lt.next 之间插入 head
                t = lt.next;
                lt.next = head;
                head.next = t;
                lt = head; // lt 后移到 head
            } else if (head.val > pivot) { // 头插法,gt 始终执行头部
                head.next = gt;
                gt = head;
            } else {
                if (eq == null) {
                    // eq 为空,需要连接 lt 的尾部
                    lt.next = head;
                    eq = head;
                } else { // 直接尾***r />                     eq.next = head;
                }
            }
            head = nxt;
        }

        if (eq != null) {
            eq.next = gt;
        } else if (tou.next != null) {
            lt.next = gt;
        } else {
            tou.next = gt;
        }

        return tou.next;
    }
}
```
发表于 2021-08-29 13:10:19 回复(1)
# include <bits/stdc++.h>
using namespace std;

struct list_node{
    int val;
    struct list_node * next;
};
#define Node list_node
int pivot;

list_node * input_list(void)
{
    int n, val;
    list_node * phead = new list_node();
    list_node * cur_pnode = phead;
    scanf("%d%d", &n, &pivot);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &val);
        if (i == 1) {
            cur_pnode->val = val;
            cur_pnode->next = NULL;
        }
        else {
            list_node * new_pnode = new list_node();
            new_pnode->val = val;
            new_pnode->next = NULL;
            cur_pnode->next = new_pnode;
            cur_pnode = new_pnode;
        }
    }
    return phead;
}
void insertHead(Node *head, Node* x) {
    if(x==NULL || head==NULL) return;
    Node* last = head->next;
    head->next = x;
    x ->next = last;
}

list_node * list_partition(list_node * head, int pivot)
{
    //////在下面完成代码
    if(head==NULL || head->next ==NULL)return head;
    Node dummy_head;
    list_node *first = head;
    
    list_node lt,gt,eq;
    Node *l = &lt,*g = &gt, *e = &eq;
    lt.next = gt.next = eq.next = NULL;
    while(first) {
         if(first ->val == pivot) {
             e ->next = first,first = first->next,e = e->next,e->next = NULL;
         }else if(first->val > pivot) {
             g ->next = first,first = first->next, g = g->next,g->next = NULL;
         }else {
             l->next = first,l = l->next,first = first->next, l->next = NULL;
         }
    }
     
    e->next = gt.next;
    l->next = eq.next;
    first = lt.next;
    
    while(first) {
        
        printf("%d ", first->val);
        
        first = first->next;
    }
    
    return lt.next;
    
    
    
    
    
    
    
}


int main ()
{
    list_node * head = input_list();
    list_partition(head, pivot);
    return 0;
}

















发表于 2021-02-02 22:37:45 回复(1)
list_node * list_partition(list_node * head, int pivot)
{
    //原理:建立一个新链表,根据比较值,把原链表一个个插入,具体分成三段。
    //小于在前,等于在中,大于在后。并且找到每段的头结点,小于时,第一段头结点在新链表头。
    //等于时,第二段表头在第一段的链尾。大于时,第三段表头在第二段链尾。再对每段进行头插法
    //mid和t用于记录第一段链尾和第二段链尾(也是第二段和第三段的表头)
    
    //p用于遍历旧链表。h,mid,t分别标记新链表三段的表头。lr用于临时指针,标记p的位置方便插入。
    //f1和f2用于下面所说的标记先后顺序和互斥的关系
    //由于都是采用头插法。
    //小于时,第一次插入的节点就是第一段的链尾,第二段的表头和还可能是第三段的表头;
    //等于时,第一次插入的节点就是第二段的链尾,第三段的表头。
    //其中,小于和等于的情况稍微复杂一点,因为小于和等于都会影响第三段表头的位置。这与它们的执行顺序有关。
    //如果小于的情况先于等于的情况插入,那么在小于的情况中,标记第二段表头mid时,还要标记第三段的表头。
    //如果等于的情况先于小于的情况插入,那么在小于的情况中,标记第二段表头mid时,不用标记第三段表头。
    //例如:k=3,先后插入2、9,5。2不光是第二段表头还是第三段表头。结果2-5-9。
    //例如:k=3,先后插入2、9、3、4、3、5第三段的表头先被设置为2,随后被设置3(第三个)。结果2-3(5)-3(3)-5-4-9
    list_node *new_head = new list_node();
    new_head->next = NULL;
    list_node *h,*mid,*t,*p,*lr;
    h = mid = t = new_head;
    p = head;
    int f1 = 1,f2 = 1;
    while(p != NULL){
        if(p->val > pivot){
                lr= p;
                p = p->next;
                lr->next = t->next;
                t->next = lr;
        }

        else if(p->val < pivot){
            if(f1 == 1 && f2 == 1){
                mid = p;
                t = p;
                f2 ++;
            }
            if(f1 == 2 && f2 == 1) {
                mid = p;
                f2++;
            }
            lr = p;
            p = p->next;
            lr->next = h->next;
            h->next = lr;
        }

        else{
            if(f1 == 1){
                t = p;
                f1++;
            }
            lr = p;
            p = p->next;
            lr->next = mid->next;
            mid->next =lr;
        }
    }
    return new_head->next;
}

发表于 2020-07-02 14:06:42 回复(0)

思路(左神版):
1.将链表存到数组中
2.利用快排的partion函数调整数组
3.将数组重新连成链表

import java.io.*;

public class Main {
    static int n, k;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        k = Integer.parseInt(str[1]);
        Node h = new Node(-1);
        Node p = h;
        String[] s1 = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            p.next = new Node(Integer.parseInt(s1[i]));
            p = p.next;
        }
        h = h.next;//真实头结点
        h = listPartion(h, k);
        while (h != null) {
            bw.write(h.val + " ");
            h = h.next;
        }
        bw.newLine();
        bw.flush();
    }

    private static Node listPartion(Node h, int k) {
        Node cur = h;
        Node[] arr = new Node[n];
        int i = 0;
        //将链表存到数组
        for (i = 0; i != n; i++) {
            arr[i] = cur;
            cur = cur.next;
        }
        //调整数组
        arrPartion(arr, k);
        //重新连成链表
        for (i = 1; i != n; i++) {
            arr[i - 1].next = arr[i];
        }
        arr[i - 1].next = null;
        return arr[0];
    }

    private static void arrPartion(Node[] arr, int k) {
        int small = -1, big = arr.length;
        int index = 0;
        while (index != big) {
            if (arr[index].val < k) {
                swap(arr, ++small, index++);
            } else if (arr[index].val == k) {
                index++;
            } else {
                swap(arr, --big, index);
            }
        }
    }

    private static void swap(Node[] arr, int i, int j) {
        Node tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
class Node {
    int val;
    Node next;

    public Node(int val) {
        this.val = val;
    }
}
发表于 2020-07-02 09:52:56 回复(0)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static class Node {

        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
        }
    }
    
    public static Node listGenerator(int length, String[] numbers) {
        Node head = new Node(Integer.parseInt(numbers[0]));
        Node cur = head;
        for (int i = 1; i < length; i++) {
            cur.next = new Node(Integer.parseInt(numbers[i]));
            cur = cur.next;
        }
        cur.next = null;
        return head;
    }
    
    public static void printList(Node head) {
        while (head != null) {
            System.out.print(head.value +" ");
            head = head.next;
        }
        System.out.println();
    }
    
    public static Node listPartition(Node head, int pivot) {
        Node lessHead = null;
        Node lessTail = null;
        Node equalHead = null;
        Node equalTail = null;
        Node moreHead = null;
        Node moreTail = null;
        Node next = null;
        while (head != null) {
            next = head.next;
            head.next = null;
            if(head.value < pivot) {
                if (lessHead == null) {
                    lessHead = head;
                    lessTail = lessHead;
                } else {
                    lessTail.next = head;
                    lessTail = lessTail.next;
                }
            } else if (head.value == pivot) {
                if (equalHead == null) {
                    equalHead = head;
                    equalTail = equalHead;
                } else {
                    equalTail.next = head;
                    equalTail = equalTail.next;
                }
            } else {
                if (moreHead == null) {
                    moreHead = head;
                    moreTail = moreHead;
                } else {
                    moreTail.next = head;
                    moreTail = moreTail.next;
                }
            }
            head = next;
        }
        if (lessHead != null) {
            lessTail.next = equalHead;
            equalTail = equalTail == null ? lessTail : equalTail;
        }
        if (equalTail != null) {
            equalTail.next = moreHead;
        }
        return lessHead != null ? lessHead : equalHead != null ? equalHead : moreHead;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] parameters = bufferedReader.readLine().split(" ");
        int n = Integer.parseInt(parameters[0]);
        int pivot = Integer.parseInt(parameters[1]);
        String[] numbers = bufferedReader.readLine().split(" ");
        Node head = listGenerator(n, numbers);
        head = listPartition(head, pivot);
        printList(head);
    }
}

不通过
您的代码已保存
运行超时:您的程序未能在规定时间内运行结束,请检查是否循环有错或算法复杂度过大。
case通过率为85.00%
发表于 2019-12-29 20:15:54 回复(0)
两种解法:
方法一:用链表时老超时,可以看看第二种方式,第一种这里用纯数组解决的。
import java.util.Scanner;

/**
 * 
 * @author minghai
 * @date 2019年9月6日
 */
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int pivot = scan.nextInt();
		
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = scan.nextInt();
		}
		
		arrPartition(arr,pivot);
        for(int a:arr){
            System.out.print(a+" ");
        }
		
	}
	

	private static void arrPartition(int[] nodeArr, int pivot) {
		int small = -1;
		int big = nodeArr.length;
		int index = 0;
		while(index != big) {
			if(nodeArr[index] < pivot) {
				swap(nodeArr,++small,index++);
			}else if(nodeArr[index] == pivot) {
				index++;
			}else {
				swap(nodeArr, --big, index);
			}
		}
	}

	private static void swap(int[] nodeArr, int i, int j) {
		int temp = nodeArr[i];
		nodeArr[i] = nodeArr[j];
		nodeArr[j] = temp;
	}
}
方法2:还是超时,不过思路很好,可以实现数据的稳定性,代码为 左神《程序员代码面试指南》中此题金阶题的代码,不过在此OJ测试中,超时,可以通过在从控制台输入时,每取到一个值就判断该值与目标值的大小或相等,然后加到对应的 大、中、小链表中,可以减少一次时间一次循环时间。

package ch02_linked;

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int pivot = scan.nextInt();
		Node head = new Node(scan.nextInt());
		Node cur = head;
		while(--n > 0) {
			cur.next = new Node(scan.nextInt());
			cur = cur.next;
		}
		cur = listPartition2(head, pivot);
		while(cur!=null) {
			System.out.print(cur.val+" ");
			cur = cur.next;
		}
	}
	
	public  static Node listPartition2(Node head, int pivot) {
		Node sH = null; 
		Node sT = null;
		Node eH = null;
		Node eT = null;
		Node bH = null;
		Node bT = null;
		Node next = null;
		while(head != null) {
			next = head.next;
			head.next = null;
			if(head.val < pivot) {
				if(sH == null) {
					sH = head;
					sT = head;
				}else {
					sT.next = head;
					sT = sT.next;
				}
			}else if(head.val == pivot) {
				if(eH == null) {
					eH = head;
					eT = head;
				}else {
					eT.next = head;
					eT = eT.next;
				}
			}else {
				if(bH == null) {
					bH = head;
					bT = head;
				}else {
					bT.next = head;
					bT = bT.next;
				}
			}
			head = next;
		}
		
		if(sT != null) {
			sT.next = eH;
			eT = eT == null ? sT : eT;
		}
		if(eT != null) {
			eT.next = bH;
		}
		return sH != null ? sH : eH != null ? eH : bH;
	}
}


发表于 2019-09-07 11:22:54 回复(0)