将一个单向链表拆分成两个java实现

落日映苍穹つ 2023-09-28 15:11 112阅读 0赞

常见的一道笔试题：链表拆分，将一个单向链表和拆分成两个，如下所示：

原始链表：1—>2—>3—>4—>5—>6—>7

拆分后链表A：1—>3—>5—>7

拆分后链表B：2—>4—>6

思路：

定义两个头节点，作为新链表的头，分别指向原链表的前两个元素

再定义两个浮动，初始值分别指向新链表的头结点

然后交替遍历原始节点，将各自的next赋值给新链表

待遍历到最后，需要为两个新链表指定尾节点，即赋值为null

最后退出循环。

class ShowMeBug {
        public static class Node {
            public int data;
            public Node next;
    
            public Node(int data, Node nxt) {
                this.data = data;
                this.next = nxt;
            }
        }
    
        /**
         * 思路，定义两个浮动游标，随之链表移动而移动，完成整个链表的遍历
         * @param head
         */
        public void solution(Node head) {
    
            Node first = head;
            Node second = head.next;
            Node curseA = first;//游标A
            Node curseB = second;//游标B
    
            while (curseB != null) {
    
                if (curseB.next != null) {
                    curseA.next = curseB.next;
                    curseA = curseA.next;
                    curseB.next = curseA.next;
                    curseB = curseB.next;
    
                } else {
                    curseA.next = null;
                    curseB.next = null;
                    break;
                }
            }
    
            printNode(first);
            printNode(second);
        }
    
        private static void printNode(Node head) {
            while (head != null) {
                System.out.println(head.data);
                head = head.next;
            }
        }
    
    
        public static void main(String[] args) {
    
            ShowMeBug showMeBug = new ShowMeBug();
    
            Node node7 = new Node(7, null);
            Node node6 = new Node(6, node7);
            Node node5 = new Node(5, node6);
            Node node4 = new Node(4, node5);
            Node node3 = new Node(3, node4);
            Node node2 = new Node(2, node3);
            Node node1 = new Node(1, node2);
    
            showMeBug.solution(node1);
            //printNode(node1);
        }
    }