JavaExample09-单向链表的倒置

1.原理

将单向链表倒置的难点是单向链表的每个节点只能指向一个节点，如果直接将链表中某一个节点指向其前一个节点，那么就找不到后面的节点了。

所以我们需要定义指针来进行操作。

定义三个指针curNode、preNode、nextNode，分别代表当前节点，当前节点的前一个节点，当前节点的后一个节点。

1. 先将nextNode移动至当前节点的后一个节点位置
2. 然后将当前节点指向前一个节点preNode位置
3. 然后将preNode移动至当前节点位置
4. 然后将curNode移动至后一个节点位置

如此循环操作，直至遍历完整个链表。

最后，让倒置前的尾节点成为新的头结点。

图示：

1.定义三个指针

2.nextNode指针移动至curNode后一个节点

3.curNode指针所代表节点指向前一个节点preNode

4.preNode指针指向curNode所代表的当前节点

5.curNode指针移动至下一个节点位置

6.nextNode指针继续移动至后一个节点位置

7.curNode所代表的节点指向前一个节点

8.preNode指针指向至当前节点

9.curNode指针移动至后一个节点

如此循环，直至遍历整个链表

2.代码实现

public void inversion() {
    //定义三个指针，分别指向当前节点，当前节点前一个节点，当前节点的后一个节点
    Node curNode = head;
    Node preNode = null;
    Node nextNode = null;
    while (curNode != null) {
        //将nextNode移动至当前节点的下一个节点位置
        nextNode = curNode.getNext();
        //然后将当前节点指向前一个节点preNode位置
        curNode.setNext(preNode);
        //然后将preNode移动至当前节点位置
        preNode = curNode;
        //然后将curNode移动至后一个节点位置
        curNode = nextNode;
    }
    //遍历完链表后使先前的尾节点成为新的头结点
    head = preNode;
}

3.完整代码

3.1节点类

/**
 * @Author: TSCCG
 * @Date: 2021/06/25 22:26
 */
public class Node{
    private Integer data;
    private Node next;

    public Node(Integer data) {
        this.data = data;
    }

    public Integer getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

3.2链表类

/**
 * @Author: TSCCG
 * @Date: 2021/06/25 22:29
 */
public class InversionLinkedList {
    private Node head;
    private int size = 0;

    /**
     * 添加节点
     * @param data 节点中的数据
     */
    public void add(Integer data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            getEnd(head).setNext(newNode);
        }
        size++;
    }

    /**
     * 找到尾节点
     * @param node 从该节点开始找
     * @return 返回尾节点
     */
    private Node getEnd(Node node) {
        if (node.getNext() == null) {
            return node;
        }
        return getEnd(node.getNext());
    }
    /**
     * 遍历节点
     */
    public void printNode() {
        Node tempNode = head;
        while (tempNode != null) {
            if (tempNode.getNext() == null) {
                System.out.println(tempNode.getData());
            } else {
                System.out.print(tempNode.getData() + ",");
            }
            tempNode = tempNode.getNext();
        }
    }
    /**
     * 链表倒置
     */
    public void inversion() {
        //定义三个指针，分别指向当前节点，当前节点前一个节点，当前节点的后一个节点
        Node curNode = head;
        Node preNode = null;
        Node nextNode = null;
        while (curNode != null) {
            //将nextNode移动至当前节点的下一个节点位置
            nextNode = curNode.getNext();
            //然后将当前节点指向前一个节点preNode位置
            curNode.setNext(preNode);
            //然后将preNode移动至当前节点位置
            preNode = curNode;
            //然后将curNode移动至后一个节点位置
            curNode = nextNode;
        }
        //遍历完链表后使先前的尾节点成为新的头结点
        head = preNode;
    }
}

3.3测试类

/**
 * @Author: TSCCG
 * @Date: 2021/06/25 22:56
 */
public class InversionTest {
    public static void main(String[] args) {
        InversionLinkedList list = new InversionLinkedList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        System.out.println("-------倒置前-------");
        list.printNode();
        System.out.println("-------倒置后-------");
        list.inversion();
        list.printNode();
    }
}

结果：

-------倒置前-------
1,2,3,4
-------倒置后-------
4,3,2,1