数据结构与算法

1. 单链表的结点结构

• data域：存储数据元素信息的域称为数据域；
• next域：存储直接后继位置的域称为指针域，它是存放结点的直接后继的地址（位置）的指针域（链域）。
• data域+ next域：组成数据ai的存储映射，称为结点；

注意

• ①链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。
• ②每个结点只有一个链域的链表称为单链表（Single Linked List）。

创建一结点类，其Java代码如下：

class Node {
    private int Data;// 数据域
    private Node Next;// 指针域
    public Node(int Data) {
        // super();
        this.Data = Data;
    }
    public int getData() {
        return Data;
    }
    public void setData(int Data) {
        this.Data = Data;
    }

    public Node getNext() {
        return Next;
    }
    public void setNext(Node Next) {
        this.Next = Next;
    }
}

2 反转的方法--递归反转法

• 在反转当前节点之前先反转后续节点。这样从头结点开始，层层深入直到尾结点才开始反转指针域的指向。
• 从尾结点开始，逆向反转各个结点的指针域指向

    /**
     * 递归，在反转当前节点之前先反转后续节点
     */
    public static Node recursiveReverse(Node currentNode) {
        if (currentNode == null || currentNode.getNext() == null) {
            return currentNode;
        }

        Node returnNode = recursiveReverse(currentNode.getNext());
        //这里是重点。
        //当前节点（currentNode）的下一个节点，正好是返回节点returnNode的最后一个节点
        currentNode.getNext().setNext(currentNode);
        currentNode.setNext(null);
        return returnNode;
    }

分析上述过程

• 1. 原始链表是1-2-3-4-5-6
• 2. 第一次调用即recursiveReverse(1)！=null && recursiveReverse(1).getNext()！=null 直到--最后一次。

• 第一次返回6
  即返回后 returnNode=6；currentNode=5-6；
  

  TIM截图20180906110411.png
  然后设置currentNode.getNext().setNext(currentNode);
  那么现在的returnNode=6-5-6...；currentNode=5-6-5-6...
  TIM截图20180906111139.png
  接着currentNode.setNext(null);
  TIM截图20180906111338.png
  此时实现了第一次的翻转 并且向上返回。

• 第二次返回

  • 返回后returnNode=6-5 returnNode= 4-5（因为上一次已将5的next置为null）
  • 然后设置currentNode.getNext().setNext(currentNode);

  • currentNode.setNext(null);

    
    TIM截图20180906113058.png

• 以此类推

3 反转的方法--遍历反转法

• 遍历反转法是从前往后反转各个结点的指针域的指向

    //思路：
    //当前节点的next不为null，则需要进行反转
    //反转即：需要将next的next设置为当前节点

    public static Node cycleReverse(Node currentNode) {

        if (currentNode == null) {
            return currentNode;
        }

        //专门记录下一个节点（依次判断下个节点是否为空）
        Node nextNode = currentNode.getNext();

        //记录next的next用于下次循环使用
        Node temp;

        //准备好第一个节点（第一个节点不需要去反转）
        currentNode.setNext(null);
        Node finalNode = currentNode;//最终返回的链表

        //如果下一个几点不为空，说明还有节点，则进行反转
        while (nextNode != null) {
            //记录元素，为了指针下移
            temp = nextNode.getNext();

            //反转链表
            nextNode.setNext(finalNode);
            finalNode = nextNode;

            //指针下移
            nextNode = temp;
        }

        return finalNode;
    }

参考

Java单链表反转 详细过程