线性表练习之Example020-将一个单链表拆分成两个链表，一个顺序一个倒序

原文链接：Example020

设 C = {a1, b1, a2, b2, ..., an, bn} 为线性表，采用带头结点的 hc 单链表存放，设计一个就地算法，将其拆分为两个线性表，使得 A = {a1, a2, ..., an}，B = {bn, ..., b2, b1}。

本题考查的知识点：

单链表通过头插法创建单链表通过尾插法创建单链表

分析：

本题可以将单链表中的节点分在两个链表 A 和 B 中。但本题要求就地修改，即可以让序号为奇数的节点保存在原链表 hc 中，然后将序号为偶数的节点倒序保存在一个新链表中。其实本题没有区分节点在链表中的序号，之所以这样说是为了能够区分将哪些节点保存在链表 A 中，哪些节点保存在链表 B 中。B 链表中的节点是采用头插法插入的，这样才能让链表节点逆序保存。 图解

核心代码：

void splitlinkedList(LNode *hc, LNode **A, LNode **B) {
    // 1.初始化单链表 A 和 B
    // 1.1 初始化单链表 A
    // 1.1.1 为链表 A 的头结点分配空间
    *A = (LNode *) malloc(sizeof(LNode));
    // 1.1.2 将头结点的 next 指针指向 null
    (*A)->next = NULL;
    // 1.2 初始化单链表 B
    // 1.2.1 为链表 B 的头结点分配空间
    *B = (LNode *) malloc(sizeof(LNode));
    // 1.2.2 将头结点的 next 指针指向 null
    (*B)->next = NULL;

    // 变量，记录链表 A 的尾节点，为了使用尾插法插入新节点，初始为链表 A 的头结点
    LNode *aTailNode = *A;
    // 变量，记录 hc 链表的结点，从头到尾扫描单链表 hc，初始为链表的第一个结点
    LNode *node = hc->next;
    // 变量，计数器，记录 hc 链表中已经遍历过的结点个数，如果是奇数则插入到链表 A 中，如果是偶数则插入到链表 B 中
    int num = 0;

    // 2.从头到尾扫描链表 hc，然后将结点分别插入到链表 A 和 B 中
    while (node != NULL) {
        // 2.1 计数器加 1，表示已经扫描过一个结点了
        num++;
        // 2.2 创建新节点（注：这里选择创建新节点的方式得到旧结点 node 的数据域值，并且将新节点的 next 指针指向 null，避免了后面再处理的问题）
        LNode *newNode = (LNode *) malloc(sizeof(LNode));
        newNode->data = node->data;
        newNode->next = NULL;
        // 2.3 判断计数器是奇数还是偶数
        // 2.3.1 如果是奇数，则采用尾插法将新节点插入到链表 A 中
        if (num % 2 != 0) {
            // 2.3.1.1 将原链表的尾节点的 next 指针指向新节点，完成新节点与链表 A 的连接
            aTailNode->next = newNode;
            // 2.3.1.2 更新变量 aTailNode，让新节点成为链表 A 的尾节点
            aTailNode = newNode;
        }
        // 2.3.2 如果是偶数，则采用头插法将新节点插入到链表 B 中
        else {
            // 2.3.2.1 将新节点的 next 指针指向原链表 B 的第一个结点（即链表 B 的头结点的后继节点），完成新节点与原链表第一个节点的连接
            newNode->next = (*B)->next;
            // 2.3.2.2 然后将链表 B 的头结点的 next 指针指向新节点，完成新节点与链表 B 头结点的连接
            (*B)->next = newNode;
        }
        // 2.4 继续 hc 链表的下一个结点
        node = node->next;
    }
}

完整代码：

#include 
#include 


typedef struct LNode {
    
    int data;
    
    struct LNode *next;
} LNode;


LNode *createByTail(LNode **list, int nums[], int n) {
    // 1.初始化单链表
    // 创建链表必须要先初始化链表，也可以选择直接调用 init() 函数
    *list = (LNode *) malloc(sizeof(LNode));
    (*list)->next = NULL;

    // 尾插法，必须知道链表的尾节点（即链表的最后一个节点），初始时，单链表的头结点就是尾节点
    // 因为在单链表中插入节点我们必须知道前驱节点，而头插法中的前驱节点一直是头节点，但尾插法中要在单链表的末尾插入新节点，所以前驱节点一直都是链表的最后一个节点，而链表的最后一个节点由于链表插入新节点会一直变化
    LNode *node = (*list);

    // 2.循环数组，将所有数依次插入到链表的尾部
    for (int i = 0; i < n; i++) {
        // 2.1 创建新节点，并指定数据域和指针域
        // 2.1.1 创建新节点，为其分配空间
        LNode *newNode = (LNode *) malloc(sizeof(LNode));
        // 2.1.2 为新节点指定数据域
        newNode->data = nums[i];
        // 2.1.3 为新节点指定指针域，新节点的指针域初始时设置为 null
        newNode->next = NULL;

        // 2.2 将新节点插入到单链表的尾部
        // 2.2.1 将链表原尾节点的 next 指针指向新节点
        node->next = newNode;
        // 2.2.2 将新节点置为新的尾节点
        node = newNode;
    }
    return *list;
}


void splitlinkedList(LNode *hc, LNode **A, LNode **B) {
    // 1.初始化单链表 A 和 B
    // 1.1 初始化单链表 A
    // 1.1.1 为链表 A 的头结点分配空间
    *A = (LNode *) malloc(sizeof(LNode));
    // 1.1.2 将头结点的 next 指针指向 null
    (*A)->next = NULL;
    // 1.2 初始化单链表 B
    // 1.2.1 为链表 B 的头结点分配空间
    *B = (LNode *) malloc(sizeof(LNode));
    // 1.2.2 将头结点的 next 指针指向 null
    (*B)->next = NULL;

    // 变量，记录链表 A 的尾节点，为了使用尾插法插入新节点，初始为链表 A 的头结点
    LNode *aTailNode = *A;
    // 变量，记录 hc 链表的结点，从头到尾扫描单链表 hc，初始为链表的第一个结点
    LNode *node = hc->next;
    // 变量，计数器，记录 hc 链表中已经遍历过的结点个数，如果是奇数则插入到链表 A 中，如果是偶数则插入到链表 B 中
    int num = 0;

    // 2.从头到尾扫描链表 hc，然后将结点分别插入到链表 A 和 B 中
    while (node != NULL) {
        // 2.1 计数器加 1，表示已经扫描过一个结点了
        num++;
        // 2.2 创建新节点（注：这里选择创建新节点的方式得到旧结点 node 的数据域值，并且将新节点的 next 指针指向 null，避免了后面再处理的问题）
        LNode *newNode = (LNode *) malloc(sizeof(LNode));
        newNode->data = node->data;
        newNode->next = NULL;
        // 2.3 判断计数器是奇数还是偶数
        // 2.3.1 如果是奇数，则采用尾插法将新节点插入到链表 A 中
        if (num % 2 != 0) {
            // 2.3.1.1 将原链表的尾节点的 next 指针指向新节点，完成新节点与链表 A 的连接
            aTailNode->next = newNode;
            // 2.3.1.2 更新变量 aTailNode，让新节点成为链表 A 的尾节点
            aTailNode = newNode;
        }
        // 2.3.2 如果是偶数，则采用头插法将新节点插入到链表 B 中
        else {
            // 2.3.2.1 将新节点的 next 指针指向原链表 B 的第一个结点（即链表 B 的头结点的后继节点），完成新节点与原链表第一个节点的连接
            newNode->next = (*B)->next;
            // 2.3.2.2 然后将链表 B 的头结点的 next 指针指向新节点，完成新节点与链表 B 头结点的连接
            (*B)->next = newNode;
        }
        // 2.4 继续 hc 链表的下一个结点
        node = node->next;
    }
}


void print(LNode *list) {
    printf("[");
    // 链表的第一个节点
    LNode *node = list->next;
    // 循环单链表所有节点，打印值
    while (node != NULL) {
        printf("%d", node->data);
        if (node->next != NULL) {
            printf(", ");
        }
        node = node->next;
    }
    printf("]n");
}

int main() {
    // 声明单链表
    LNode *hc;
    int nums[] = {1, 2, 3, 4, 5, 6, 7, 8};
    int n = 8;
    createByTail(&hc, nums, n);
    print(hc);

    // 调用函数，拆分链表
    LNode *A;
    LNode *B;
    splitlinkedList(hc, &A, &B);
    print(A);
    print(B);
}

执行结果：

[1, 2, 3, 4, 5, 6, 7, 8]
[1, 3, 5, 7]
[8, 6, 4, 2]

如果是原地拆分链表的话，代码如下：

#include 
#include 


typedef struct LNode {
    
    int data;
    
    struct LNode *next;
} LNode;


LNode *createByTail(LNode **list, int nums[], int n) {
    // 1.初始化单链表
    // 创建链表必须要先初始化链表，也可以选择直接调用 init() 函数
    *list = (LNode *) malloc(sizeof(LNode));
    (*list)->next = NULL;

    // 尾插法，必须知道链表的尾节点（即链表的最后一个节点），初始时，单链表的头结点就是尾节点
    // 因为在单链表中插入节点我们必须知道前驱节点，而头插法中的前驱节点一直是头节点，但尾插法中要在单链表的末尾插入新节点，所以前驱节点一直都是链表的最后一个节点，而链表的最后一个节点由于链表插入新节点会一直变化
    LNode *node = (*list);

    // 2.循环数组，将所有数依次插入到链表的尾部
    for (int i = 0; i < n; i++) {
        // 2.1 创建新节点，并指定数据域和指针域
        // 2.1.1 创建新节点，为其分配空间
        LNode *newNode = (LNode *) malloc(sizeof(LNode));
        // 2.1.2 为新节点指定数据域
        newNode->data = nums[i];
        // 2.1.3 为新节点指定指针域，新节点的指针域初始时设置为 null
        newNode->next = NULL;

        // 2.2 将新节点插入到单链表的尾部
        // 2.2.1 将链表原尾节点的 next 指针指向新节点
        node->next = newNode;
        // 2.2.2 将新节点置为新的尾节点
        node = newNode;
    }
    return *list;
}


LNode *splitlinkedList(LNode *hc) {
    // 创建存储序号为偶数节点的链表 B，并初始化头结点
    LNode *B = (LNode *) malloc(sizeof(LNode));
    B->next = NULL;
    // 链表 A，其实就是删除了一些节点后的链表 hc
    LNode *A = hc;
    LNode *aTailNode = hc;// 记录链表 A 的尾节点，用于尾插法

    // 从头到尾扫描链表 hc，记录链表 hc 中的节点，初始为第一个节点
    LNode *node = hc->next;
    LNode *temp;
    while (node != NULL) {
        // 将 node 节点保存到链表 A 中，采用尾插法
        aTailNode->next = node;
        aTailNode = node;

        // 然后链表 hc 的结点向前移动一个
        node = node->next;

        // 此时 node 结点已经后移一个了，所以要把这个结点插入到链表 B 中，前提是该结点存在
        if (node != NULL) {
            // 临时保存 node 结点的后继节点
            temp = node->next;

            // 采用头插法，将 node 节点插入到链表 B 的头部
            node->next = B->next;
            B->next = node;

            // 将节点插入到链表 B 头部后，此时 hc 链表的节点也该继续向后移动一个位置
            node = temp;
        }
    }
    // 由于是摘除节点插入到链表 A 的尾部，所以要将链表 A 的尾节点的 next 指针指向 null
    aTailNode->next = NULL;

    // 返回创建成功的单链表 B，保存了链表 hc 中序号为偶数的节点
    return B;
}


void print(LNode *list) {
    printf("[");
    // 链表的第一个节点
    LNode *node = list->next;
    // 循环单链表所有节点，打印值
    while (node != NULL) {
        printf("%d", node->data);
        if (node->next != NULL) {
            printf(", ");
        }
        node = node->next;
    }
    printf("]n");
}

int main() {
    // 声明单链表
    LNode *hc;
    int nums[] = {1, 2, 3, 4, 5, 6, 7, 8};
    int n = 8;
    createByTail(&hc, nums, n);
    print(hc);

    // 调用函数，拆分链表
    LNode *B = splitlinkedList(hc);
    print(hc);
    print(B);
}

核心代码：

    
    public void splitlinkedList(linkedList A, linkedList B) {
        // 1.初始化单链表 A 和 B
        // 1.1 初始化单链表 A
        // 1.1.1 为链表 A 的头结点分配空间
        A.list=new LNode();
        // 1.1.2 将头结点的 next 指针指向 null
        A.list.next=null;
        // 1.2 初始化单链表 B
        // 1.2.1 为链表 B 的头结点分配空间
        B.list=new LNode();
        // 1.2.2 将头结点的 next 指针指向 null
        B.list.next=null;

        // 变量，记录链表 A 的尾节点，为了使用尾插法插入新节点，初始为链表 A 的头结点
        LNode aTailNode=A.list;
        // 变量，记录 hc 链表的结点，从头到尾扫描单链表 hc，初始为链表的第一个结点
        LNode node=list.next;
        // 变量，计数器，记录 hc 链表中已经遍历过的结点个数，如果是奇数则插入到链表 A 中，如果是偶数则插入到链表 B 中
        int num=0;

        // 2.从头到尾扫描链表 hc，然后将结点分别插入到链表 A 和 B 中
        while (node!=null){
            // 2.1 计数器加 1，表示已经扫描过一个结点了
            num++;
            // 2.2 创建新节点（注：这里选择创建新节点的方式得到旧结点 node 的数据域值，并且将新节点的 next 指针指向 null，避免了后面再处理的问题）
            LNode newNode=new LNode();
            newNode.data= node.data;
            newNode.next=null;
            // 2.3 判断计数器是奇数还是偶数
            // 2.3.1 如果是奇数，则采用尾插法将新节点插入到链表 A 中
            if(num%2!=0){
                // 2.3.1.1 将原链表的尾节点的 next 指针指向新节点，完成新节点与链表 A 的连接
                aTailNode.next=newNode;
                // 2.3.1.2 更新变量 aTailNode，让新节点成为链表 A 的尾节点
                aTailNode=newNode;
            }
            // 2.3.2 如果是偶数，则采用头插法将新节点插入到链表 B 中
            else {
                // 2.3.2.1 将新节点的 next 指针指向原链表 B 的第一个结点（即链表 B 的头结点的后继节点），完成新节点与原链表第一个节点的连接
               newNode.next=B.list.next;
                // 2.3.2.2 然后将链表 B 的头结点的 next 指针指向新节点，完成新节点与链表 B 头结点的连接
               B.list.next=newNode;
            }
            // 2.4 继续 hc 链表的下一个结点
            node=node.next;
        }
    }

完整代码：

public class linkedList {
    
    private LNode list;

    
    public LNode createByTail(int... nums) {
        // 1.初始化单链表
        // 创建链表必须要先初始化链表，也可以选择直接调用 init() 函数
        list = new LNode();
        list.next = null;

        // 尾插法，必须知道链表的尾节点（即链表的最后一个节点），初始时，单链表的头结点就是尾节点
        // 因为在单链表中插入节点我们必须知道前驱节点，而头插法中的前驱节点一直是头节点，但尾插法中要在单链表的末尾插入新节点，所以前驱节点一直都是链表的最后一个节点，而链表的最后一个节点由于链表插入新节点会一直变化
        LNode tailNode = list;

        // 2.循环数组，将所有数依次插入到链表的尾部
        for (int i = 0; i < nums.length; i++) {
            // 2.1 创建新节点，并指定数据域和指针域
            // 2.1.1 创建新节点，为其分配空间
            LNode newNode = new LNode();
            // 2.1.2 为新节点指定数据域
            newNode.data = nums[i];
            // 2.1.3 为新节点指定指针域，新节点的指针域初始时设置为 null
            newNode.next = null;

            // 2.2 将新节点插入到单链表的尾部
            // 2.2.1 将链表原尾节点的 next 指针指向新节点
            tailNode.next = newNode;
            // 2.2.2 将新节点置为新的尾节点
            tailNode = newNode;
        }

        return list;
    }

    
    public void splitlinkedList(linkedList A, linkedList B) {
        // 1.初始化单链表 A 和 B
        // 1.1 初始化单链表 A
        // 1.1.1 为链表 A 的头结点分配空间
        A.list=new LNode();
        // 1.1.2 将头结点的 next 指针指向 null
        A.list.next=null;
        // 1.2 初始化单链表 B
        // 1.2.1 为链表 B 的头结点分配空间
        B.list=new LNode();
        // 1.2.2 将头结点的 next 指针指向 null
        B.list.next=null;

        // 变量，记录链表 A 的尾节点，为了使用尾插法插入新节点，初始为链表 A 的头结点
        LNode aTailNode=A.list;
        // 变量，记录 hc 链表的结点，从头到尾扫描单链表 hc，初始为链表的第一个结点
        LNode node=list.next;
        // 变量，计数器，记录 hc 链表中已经遍历过的结点个数，如果是奇数则插入到链表 A 中，如果是偶数则插入到链表 B 中
        int num=0;

        // 2.从头到尾扫描链表 hc，然后将结点分别插入到链表 A 和 B 中
        while (node!=null){
            // 2.1 计数器加 1，表示已经扫描过一个结点了
            num++;
            // 2.2 创建新节点（注：这里选择创建新节点的方式得到旧结点 node 的数据域值，并且将新节点的 next 指针指向 null，避免了后面再处理的问题）
            LNode newNode=new LNode();
            newNode.data= node.data;
            newNode.next=null;
            // 2.3 判断计数器是奇数还是偶数
            // 2.3.1 如果是奇数，则采用尾插法将新节点插入到链表 A 中
            if(num%2!=0){
                // 2.3.1.1 将原链表的尾节点的 next 指针指向新节点，完成新节点与链表 A 的连接
                aTailNode.next=newNode;
                // 2.3.1.2 更新变量 aTailNode，让新节点成为链表 A 的尾节点
                aTailNode=newNode;
            }
            // 2.3.2 如果是偶数，则采用头插法将新节点插入到链表 B 中
            else {
                // 2.3.2.1 将新节点的 next 指针指向原链表 B 的第一个结点（即链表 B 的头结点的后继节点），完成新节点与原链表第一个节点的连接
               newNode.next=B.list.next;
                // 2.3.2.2 然后将链表 B 的头结点的 next 指针指向新节点，完成新节点与链表 B 头结点的连接
               B.list.next=newNode;
            }
            // 2.4 继续 hc 链表的下一个结点
            node=node.next;
        }
    }

    
    public void print() {
        // 链表的第一个节点
        LNode node = list.next;
        // 循环打印
        String str = "[";
        while (node != null) {
            // 拼接节点的数据域
            str += node.data;
            // 只要不是最后一个节点，那么就在每个节点的数据域后面添加一个分号，用于分隔字符串
            if (node.next != null) {
                str += ", ";
            }
            // 继续链表的下一个节点
            node = node.next;
        }
        str += "]";
        // 打印链表
        System.out.println(str);
    }
}


class LNode {
    
    int data;
    
    LNode next;
}

测试代码：

public class linkedListTest {
    public static void main(String[] args) {
        // 创建单链表
        linkedList list = new linkedList();
        list.createByTail(1, 2, 3, 4, 5, 6, 7, 8);
        list.print();

        // 调用函数拆分链表
        linkedList A = new linkedList();
        linkedList B = new linkedList();
        list.splitlinkedList(A, B);
        A.print();
        B.print();
    }
}

执行结果：

[1, 2, 3, 4, 5, 6, 7, 8]
[1, 3, 5, 7]
[8, 6, 4, 2]