算法例子:拆分(按照奇偶位置)双向链表为两个链表(Java)

1.例子描述

将一个双向链表,按照奇偶位置进行拆分成两个链表
即:
1.双向链表中偶数位置的结点组成一个链表.
2.双向链表中奇数位置的结点组成一个链表.
3.拆分完成后,双向链表变成了空链表.

2.打印结果

待分割的链表:
head->tail:[1,2,3,4,5,6,7,8,9,10]
---------存储偶数位置结点的链表----------
head->tail:[2,4,6,8,10]
tail-->head:[10,8,6,4,2]
---------存储奇数位置结点的链表----------
head->tail:[1,3,5,7,9]
tail-->head:[9,7,5,3,1]
---------打印被分割的链表(此时成了一个空链表)----
head->tail:[]

3.思路流程图

4.思路设计

1.创建双向链表结点数据结构.
2.创建双向链表数据结构.
2.1.在双向链表中创建添加结点的方法.
2.2.在双向链表中创建打印链表的方法.
3.创建拆分方法.
3.1.定义一个计数器.
3.2.遍历待拆分的双向链表.
3.3.当计数器为偶数时,插入到存储偶数位置结点的链表中.
3.4.当计数器为奇数时,插入到存储奇数位置结点的链表中.
4.处理一些特殊位置的结点.
4.1.存储偶数位置的链表的头结点的前指针未覆盖,则需要置为null
4.2.当待拆分链表的结点个数为偶数时,那么存储奇数位置链表的尾结点的next指针未被覆盖,则需要置为null.
4.3.当待拆分链表的结点个数为奇数时,那么存储偶数位置链表的尾结点的next指针未被覆盖,则需要置为null.

5.代码实现

5.1 定义双向链表结点数据结构

class DoubleDirectionNode {
    public int value;//当前的值
    public DoubleDirectionNode pre;//前一个结点
    public DoubleDirectionNode next;//后一个结点

    public DoubleDirectionNode(int value, DoubleDirectionNode pre, DoubleDirectionNode next) {
        this.value = value;
        this.pre = pre;
        this.next = next;
    }
}

5.2 定义双向链表数据结构

public class DoubledirectionList {
    public DoubleDirectionNode head;//头结点
    public DoubleDirectionNode tail;//尾结点

    /**
     * 添加结点,顺序添加
     *
     * @param node
     */
    public void addNode(DoubleDirectionNode node) {
        //1.先将结点pre和next指针置为null
        if (node == null) {
            return;
        }
        //2.判断当前链表为null.则将插入的结点置为链表的head和tail结点
        if (head == null) {
            head = tail = node;
        } else {
            //3.往尾部插入
            //3.1.tail结点的next指向插入的结点
            tail.next = node;
            //3.2.插入的结点的pre指向前一个结点
            node.pre = tail;
            //3.3.尾结点指向当前结点
            tail = node;
        }
    }

    /**
     * 打印链表:从前往后
     */
    public void printlnListHeadToTail() {
        System.out.print("head->tail:");
        DoubleDirectionNode temp = head;
        int flag = 0;
        System.out.print("[");
        while (temp != null) {
            if (flag == 0) {
                System.out.print(temp.value);
                flag = 1;
            } else {
                System.out.print("," + temp.value);
            }
            temp = temp.next;
        }
        System.out.println("]");
    }

    /**
     * 打印链表:从后往前
     */
    public void printlnListTailToHead() {
        System.out.print("tail-->head:");
        DoubleDirectionNode temp = tail;
        int flag = 0;
        System.out.print("[");
        while (temp != null) {
            if (flag == 0) {
                System.out.print(temp.value);
                flag = 1;
            } else {
                System.out.print("," + temp.value);
            }
            temp = temp.pre;
        }
        System.out.println("]");
    }
}

5.3 定义拆分双向链表方法

 /**
     * 拆分双向链表为两个链表(分割规则:按照结点位置奇偶性拆分)
     *
     * @param doubleList    被分割的链表
     * @param splitEvenList 分割后存储偶数位置的链表
     * @param splitOddList  分割后存储奇数位置的链表
     */
    public static void splitDoubledirectionList(DoubledirectionList doubleList,
                                                DoubledirectionList splitEvenList,
                                                DoubledirectionList splitOddList) {
        //1.判断是否为空
        if (doubleList == null || splitEvenList == null || splitOddList == null) {
            return;
        }
        //2.计数器
        int count = 0;
        //3.遍历的链表
        while (doubleList.head != null) {
            //4.计数器+1
            count++;
            if (count % 2 == 0) {
                //3.1.偶数位置:添加到偶数链表
                splitEvenList.addNode(doubleList.head);
            } else {
                //3.2.奇数位置:添加奇数链表
                splitOddList.addNode(doubleList.head);
            }
            doubleList.head = doubleList.head.next;
        }
        //5.将链表倒数第二个位置的结点的next指针置为null.
        if (count % 2 == 0) {
            //表示最后一个是偶数位置结点,那么倒数第二个结点则是奇数结点位置
            splitOddList.tail.next = null;
        } else {
            //最后一个是奇数位置结点,那么倒数第二个结点则是偶数结点位置
            splitEvenList.tail.next = null;
        }
        //4.将存储偶数位置结点的head的pre去掉.
        if (splitEvenList.head != null) {
            splitEvenList.head.pre = null;
        }
    }

5.4 调用示例

public static void main(String[] agrs) {
        DoubledirectionList doubleList = new DoubledirectionList();

        //1.创建一个双向链表,并插入数据:例子是插入1...10
        for (int i = 1; i <= 10; i++) {
            doubleList.addNode(new DoubleDirectionNode(i, null, null));
        }
        System.out.println("待分割的链表:");
        doubleList.printlnListHeadToTail();
        //2.定义存储技术和偶数的链表
        DoubledirectionList splitEvenList = new DoubledirectionList();
        DoubledirectionList splitOddList = new DoubledirectionList();
        //3.调用分割链表
        splitDoubledirectionList(doubleList, splitEvenList, splitOddList);
        //4.打印分割结果
        System.out.println("---------存储偶数位置结点的链表----------");
        splitEvenList.printlnListHeadToTail();
        splitEvenList.printlnListTailToHead();
        System.out.println("---------存储奇数位置结点的链表----------");
        splitOddList.printlnListHeadToTail();
        splitOddList.printlnListTailToHead();
        //5.打印被分割的链表,此时成了一个空链表
        System.out.println("---------打印被分割的链表(此时成了一个空链表)----");
        doubleList.printlnListHeadToTail();
    }

6.总结

6.1 复杂度

时间复杂度:O(N)
控件复杂度:O(1)

6.2 其他思路:

1.遍历链表时,也可以取出结点中的值,然后创建新结点,将值赋给此新结点,插入到对应的拆分链表中.
2.优点:虽然这样不需要处理特殊位置的结点
3.缺点:这样又创建了n个结点,空间复杂度为O(N).