小猪学算法-反转链表

迭代写法

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode pre = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    return pre;
}

通过循环遍历的方式，使链表的每一个节点和它的下一个节点断开，然后重置其下一个节点。

对于链表中的一个节点(cur)来说，它包含节点的值（value）、其所指向的下一个节点（next）、及指向它的上一个节点（pre）。反转链表就是要把当前节点指向的下一个节点变成指向上一个节点。（链表头没有上一个节点，链表尾下一个节点的指向为空）

• next = cur.next; 保留当前节点的下一个节点

• cur.next = pre; 重置当前节点的下一个节点为上一个节点

• pre = cur; 下次遍历需要用到的上一个节点

• cur = next; 下次遍历需要用到的当前节点

递归写法

class Solution {
    public ListNode reverseList1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 5-4-3-2-1   => 5-(1-2-3-4)
        // 这里假想后面部分已经完成了旋转,而不必陷入到具体的反转递归逻辑陷阱里面去
        // head.next = 1-2-3-4
        // node = 5-(1-2-3-4)
        ListNode node = reverseList1(head.next);
        // (1-2-3-4)-5-(1-2-3-4) 此时是存在一个环的
        head.next.next = head;
        // 把环断开,也就是把上一步的后面的括号部分给断开 (1-2-3-4)-5
        head.next = null;
        return node;
    }

赏

谢谢你请我吃糖果