算法初级——单链表划分区域

将单向链表按某值划分成左边小、中间相等、右边大的形式
【题目】 给定一个单向链表的头节点head,节点的值类型是整型,再给定一个整 数pivot。实现一个调整链表的函数,将链表调整为左部分都是值小于 pivot的节点,中间部分都是值等于pivot的节点,右部分都是值大于 pivot的节点。除这个要求外,对调整后的节点顺序没有更多的要求。 例如:链表9->0->4->5->1,pivot=3。 调整后链表可以是1->0->4->9->5,也可以是0->1->9->5->4。总之,满 足左部分都是小于3的节点,中间部分都是等于3的节点(本例中这个部 分为空),右部分都是大于3的节点即可。对某部分内部的节点顺序不做要求。

进阶: 在原问题的要求之上再增加如下两个要求。
在左、中、右三个部分的内部也做顺序要求,要求每部分里的节点从左 到右的顺序与原链表中节点的先后次序一致。 例如:链表9->0->4->5->1,pivot=3。调整后的链表是0->1->9->4->5。 在满足原问题要求的同时,左部分节点从左到右为0、1。在原链表中也是先出现0,后出现1;中间部分在本例中为空,不再讨论;右部分节点从左到右为9、4、5。在原链表中也是先出现9,然后出现4,最后出现5。
如果链表长度为N,时间复杂度请达到O(N),额外空间复杂度请达到O(1)。
/*
* **先统计单链表的长度,新建一个对应长度大小的node类型数组,遍历单链表,将单链表所有元素都添加进数组,然后将数组进行小中大
* 划分,然后将排完序的数组个元素再连接成单链表,返回头结点。
*
* **定义小中大三个区域的前后节点,然后每次读取新节点后与中值比较,进行next链接,最后将所有的连接到一起
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
public class 单链表划分区域 {
    public static class Node {
        public int value;
        public Node next;
        public Node(int data) {
            this.value = data;
        }
    }
    //不考虑内部顺序
    public static Node listpar(Node head,int pivot) {
        if(head == null) {
            return head;
        }
        Node cur = head;
        int i = 0;
        while(cur != null) { //统计长度
            i++;
            cur = cur.next;
        }
        Node[] nodeArr = new Node[i];
        i = 0;
        cur = head;
        for (i = 0;i != nodeArr.length;i++) {
            nodeArr[i] = cur;
            cur = cur.next;
        }
        arrpar(nodeArr,pivot);
        for(i = 1;i != nodeArr.length;i++) {
            nodeArr[i-1].next = nodeArr[i];
        }
        nodeArr[i-1].next = null;
        return nodeArr[0];
    }
    //数组小中大划分
    private static void arrpar(Node[] nodeArr, int pivot) {
        int small = -1;
        int big = nodeArr.length;
        int index = 0;
        while (index != big) {
            if(nodeArr[index].value < pivot) {
                swap(nodeArr,++small,index++);
            }else if(nodeArr[index].value == pivot) {
                index++;
            }else {
                swap(nodeArr, --big, index);
            }
        }
    }
    //交换
    private static void swap(Node[] nodeArr, int a, int b) {
        Node tmp = nodeArr[a];
        nodeArr[a] = nodeArr[b];
        nodeArr[b] = tmp;
    }
    //打印
    public static void printLinkedList(Node node) {
        System.out.print("Linked List: ");
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }
        System.out.println();
    }
    //考虑内部顺序
    public static Node listpar2(Node head,int pivot) {
        Node sH = null; // small head
        Node sT = null; // small tail
        Node eH = null; // equal head
        Node eT = null; // equal tail
        Node bH = null; // big head
        Node bT = null; // big tail
        Node next = null;
        while (head != null) {
            next = head.next;
            head.next = null;
            if(head.value < pivot) {
                if(sH == null) {
                    sH = head;
                    sT = head;
                }else {
                    sT.next = head;
                    sT = head;
                }
            }else if (head.value == pivot) {
                if (eH == null) {
                    eH = head;
                    eT = head;
                } else {
                    eT.next = head;
                    eT = head;
                }
            } else {
                if (bH == null) {
                    bH = head;
                    bT = head;
                } else {
                    bT.next = head;
                    bT = head;
                }
            }
            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;
       
    }
    public static void main(String[] args) {
        Node head1 = new Node(7);
        head1.next = new Node(9);
        head1.next.next = new Node(2);
        head1.next.next.next = new Node(8);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(1);
        head1.next.next.next.next.next.next = new Node(5);
        printLinkedList(head1);
        //head1 = listpar(head1, 5);
        head1 = listpar2(head1, 5);
        printLinkedList(head1);

    }

}
0 条评论
发表一条评论