反转单向链表

1. 要求

转换前 : 1 -> 2 -> 3 -> 4 -> 5
转换后 : 5 -> 4 -> 3 -> 2 -> 1

转换前 : null
转换后 : null

转换前 : 5
转换后 : 5

2. 链表结构

@Data
@AllArgsConstructor
@NoArgsConstructor
static class Node {

    private int id;
    private Node next;

    public Node(int id) {
        this.id = id;
    }
}

3. 实现方式

循环、迭代

3.1 循环

/**
 * 反转链表，实现方式：循环
 *
 * @param head 链表头部
 * @return 新的链表头部
 */
public static Node reversalByCirculation(Node head) {
    if (head == null || head.next == null) {
        return head;
    }
    Node current = head;
    Node pre = null;
    while (current.next != null) {
        Node next = current.next;
        current.next = pre;
        pre = current;
        current = next;
    }
    current.next = pre;
    return current;
}

@Test
public void testReversalByCirculation() {
    Node node1 = new Node(1);
    Node node2 = new Node(2);
    Node node3 = new Node(3);
    Node node4 = new Node(4);
    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    originalHead = node1;
    Node current = reversalByCirculation(node1);
    while (current != null) {
        System.out.printf("%s ", current.id);
        current = current.next;
    }
}

3.2 迭代

private static Node originalTail;
private static Node originalHead;

/**
 * 反转链表，实现方式：迭代
 * <p>
 * originalHead：原来的链表头部 == 新的尾巴
 * originalTail：原来的链表尾巴 == 新的头部
 *
 * @param node 链表头部
 * @return 新的链表尾巴
 */
public static Node reversalByRecursion(Node node) {
    if (node == null || node.next == null) {
        originalTail = node;
        return node;
    }
    Node tail = reversalByRecursion(node.next);
    tail.next = node;
    if (node == originalHead) {
        node.next = null;
    }
    return node;
}

@Test
public void testReversalByRecursion() {
    Node node1 = new Node(1);
    Node node2 = new Node(2);
    Node node3 = new Node(3);
    Node node4 = new Node(4);
    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    originalHead = node1;
    Node newTail = reversalByRecursion(node1);
    Node current = originalTail;
    while (current != null) {
        System.out.printf("%s ", current.id);
        current = current.next;
    }
}