06、数据结构与算法 - 实战：单链表1

题目1：向有序链表中插入一个结点
思路：遍历链表，找到存放元素的正确结点位置后，插入结点

/**
 * 向有序链表中插入一个结点
 * @param headNode 有序链表的头结点
 * @param newNode 需要插入的结点
 * @return 插入结点后的有序链表
 */
public static ListNode insertIntoSortedList(ListNode headNode, ListNode newNode) {
    // 判断链表是否为空
    if (headNode == null) {
        return newNode;
    }
    // 寻找正确位置，以及该位置的前驱结点
    ListNode previousNode = null;
    ListNode currentNode = headNode;
    while ((currentNode != null) && (currentNode.getData() < newNode.getData())) {
        previousNode = currentNode;
        currentNode = currentNode.getNext();
    }
    // 插入结点
    previousNode.setNext(newNode);
    newNode.setNext(currentNode);
    // 返回有序链表的头结点
    return headNode;
}

题目2：逆置单向链表
思路1：利用栈实现
1）先获取单链表的长度，并创建相应长度的栈；
2）将单链表的数据一个一个存到栈中，然后利用栈先入后出的特性
3）从栈中取出数据生成新的单链表，即原单链表的逆置链表
思路2：使用迭代
此处使用迭代方法实现

/**
 * 逆置单向链表
 * @param headNode 链表的头结点
 * @return 逆置后的链表
 */
public static ListNode reverseList(ListNode headNode) {
    // 已经被逆置的结点(准确说是原链表中当前结点的前驱结点)
    ListNode tempNode = null;
    // 即将被逆置的结点的下一个结点(准确说是原链表中当前结点的后继结点)
    ListNode nextNode = null;

    while (headNode != null) {
        // 先找到将被逆置的结点的下一个结点(也就是原链表中当前结点的后继结点)
        nextNode = headNode.getNext();
        // 使当前结点的next指针指向上一个被逆置过的结点(也就是指向原链表中当前结点的前驱结点)
        headNode.setNext(tempNode);
        // 逆置结束，将当前结点标记为已经被逆置的结点
        tempNode = headNode;
        // 寻找下一个即将被逆置的结点
        headNode = nextNode;
    }
    // 返回被逆置的链表头结点
    return tempNode;
}

题目3：如何从单链表的表尾开始输出该链表
思路1：先将链表逆置，然后遍历输出

/**
 * 从单链表的表尾开始输出该链表
 * @param headNode 链表的头结点
 */
public static void printListFromEnd2(ListNode headNode) {
    if (headNode != null) {
        ListNode currentNode = reverseList(headNode);
        while (currentNode != null) {
            System.out.print(currentNode.getData() + " ");
            currentNode = currentNode.getNext();
        }
        System.out.println();
    }
}

思路2：使用递归实现

/**
 * 从单链表的表尾开始输出该链表
 * @param headNode 链表的头结点
 */
public static void printListFromEnd1(ListNode headNode) {
    if (headNode != null) {
        printListFromEnd1(headNode.getNext());
        System.out.print(headNode.getData() + " ");
    }
}