如何实现链表的反转

数据结构与算法

关键点在于连接新的表前先要保存一下下一个节点，否则原链表会断开，无法继续进行

class ListNode {
    int val;
    ListNode next;
    public ListNode(int val) {
        this.val = val;
    }
}
public class Solution {
    //k为倒数
    public ListNode reserve(ListNode head) {
        ListNode p = head;
        ListNode dummy = null;
        ListNode q;
        while (p != null) {
            q = p.next;//先保存一下原链表的下一个节点
            p.next = dummy;
            dummy = p;
            p = q;//取出保存位置
        }
        return dummy;
    }
    public void print(ListNode head) {
        while (head != null) {
            System.out.print(" " + head.val);
            head = head.next;
        }
    }
    public ListNode getListNode() {
        ListNode head = null;
        ListNode p = null;
        for (int i = 0; i < 10; i++) {
            ListNode node = new ListNode(i);
            if (head == null) {
                head = node;
                p = head;
            } else {
                p.next = node;
                p = p.next;
            }
        }
        return head;
    }
    public static void main(String[] args) {
        ListNode head;
        Solution solution = new Solution();
        head = solution.getListNode();
        solution.print(head);
        System.out.println();
        solution.print(solution.reserve(head));
    }
}

测试

0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0