【链表】-Lc86-基于基准值拆分链表（bigHead, bigTail, smallHead, smallTail）

写在前面

  最近想复习一下数据结构与算法相关的内容，找一些题来做一做。如有更好思路，欢迎指正。

---

---

一、场景描述

  以给基准值 x，将链表分割成 2 部分，所有小于 x 的结点排在大于或等于 x 的结点之前。请返回重新排列后的链表的头指针。

注意：
分割以后保持原来的数据顺序不变。

示例：
9->5->2->7->3, 基准值是4
返回 2->3->9->5->7
1
2
3

---

二、具体步骤

1.环境说明

2.代码

以下为Java版本实现：

public class Lc86_splitListByBase {

    public static void main(String[] args) {
        ListNode n5 = new ListNode(3);
        ListNode n4 = new ListNode(7, n5);
        ListNode n3 = new ListNode(2, n4);
        ListNode n2 = new ListNode(5, n3);
        ListNode head = new ListNode(9, n2);

        ListNode.print(head);

        System.out.println();

        ListNode.print(splitListByBase(head, 4));
    }

    /**
     *
     * 约束条件：
     * 保持原有链表值的想对位置
     *
     * 目标：返回一条新的链表
     *
     * 思路：
     *
     * 循环链表，然后与 base 的值比较，拆分成 2 个链表 small（smallHead、smallTail），big（bigHead，bigTail）
     * smallHead 和 bigHead 都是哑结点，smallTail 和 bigTail初始化时分别指向各自的 head，之后随着循环向后移动
     * 最后，把small和big连接在一起，即 smallTail.next = bigHead.next
     *
     * 定义2个链表，bigHead（哑节点），smallHead(哑节点)，bigTail = bigHead, smallTail = smallHead;
     * while循环链表
     * 如果链表 head.val < base, 那么 smallTail.next = new ListNode(head.val); smallTail = smallTail.next; head=head.next
     * 否则, bigTail.next = new ListNode(head.val); bigTail = bigTail.next; head=head.next
     *
     * 因为小于 base 的结点排在大于或等于 base 的结点之前，也就是 small 链表要放在 big 链表的前面
     * 也即 smallTail.next = bigHead.next;
     *
     * 最后返回 smallHead.next
     *
     * @param head
     * @param base
     * @return
     */
    private static ListNode splitListByBase(ListNode head, int base) {
        ListNode smallHead = new ListNode();
        ListNode bigHead = new ListNode();

        ListNode smallTail = smallHead, bigTail = bigHead;
        while (head != null) {
            if (head.val < base) {
                smallTail.next = new ListNode(head.val);
                smallTail = smallTail.next;
            } else {
                bigTail.next = new ListNode(head.val);
                bigTail = bigTail.next;
            }

            head = head.next;
        }

        smallTail.next = bigHead.next;

        return smallHead.next;
    }

    static class ListNode {
        int val;
        ListNode next;

        public ListNode() {
        }

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

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

        public static void print(ListNode head) {
            while (head != null) {
                if (head.next == null) {
                    System.out.print(head.val);
                } else {
                    System.out.print(head.val + ", ");
                }
                head = head.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

---

写在后面

  如果本文内容对您有价值或者有启发的话，欢迎点赞、关注、评论和转发。您的反馈和陪伴将促进我们共同进步和成长。