牛客题霸NC78 Java版答案

牛客题霸NC78 Java版答案

题目链接

题目思路以及解释见下面代码的注释

public ListNode ReverseList(ListNode head) {
        if (head == null) return head;
        ListNode pre = head;//上一节点
        ListNode cur = head.next;//当前节点
        ListNode temp;// 临时结点，用于保存当前结点的指针域（即下一结点）
        while (cur != null) {
            temp = cur.next;
            cur.next = pre;// 反转指针域的指向
            // 指针往下移动
            pre = cur;
            cur = temp;
        }
        // 最后将原链表的头节点的指针域置为null，还回新链表的头结点，即原链表的尾结点
        head.next = null;
        return pre;
    }

递归版本实现 见代码注释

public ListNode ReverseList(ListNode head) {
      // head，head.next是当前结点，cur是反转后新链表的头结点
        if (head == null || head.next == null) {
            return head;// 若为空链或者当前结点在尾结点，则直接还回
        }
        ListNode cur = ReverseList(head.next);//先反转后续节点head.getNext() 
        head.next.next = head;//将当前结点的指针域指向前一结点
        head.next = null;//前一结点的指针域令为null
        return cur;//反转后新链表的头结点
    }