反转单链表

本是古典何须时尚 2022-11-30 01:46 308阅读 0赞

[https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=13&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking][https_www.nowcoder.com_practice_75e878df47f24fdc9dc3e400ec6058ca_tpId_13_rp_1_ru_2Fta_2Fcoding-interviews_qru_2Fta_2Fcoding-interviews_2Fquestion-ranking]

### 一、问题描述 ###

输入一个链表，反转链表后，输出新链表的表头。

### 二、代码实现 ###

/*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class Solution {
        
        //迭代
        public ListNode ReverseList(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            
            ListNode newHead = null;
            
            while (head != null) {
                //从原链表中删除头部一个元素cur
                ListNode cur = head;    //cur.next = null;  这里无需这么做，在别处最好加上避免出现环
                head = head.next;
                //将删除的元素cur添加到新链表中（采用头插法）
                cur.next = newHead;
                newHead = cur;
            }
            
            return newHead;
        }
        
        
        //递归
        public ListNode ReverseList1(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            
            ListNode next = head.next;
            head.next = null;
            ListNode newHead = ReverseList(next);
            next.next = head;
            return newHead;
        }
        
    }

[https_www.nowcoder.com_practice_75e878df47f24fdc9dc3e400ec6058ca_tpId_13_rp_1_ru_2Fta_2Fcoding-interviews_qru_2Fta_2Fcoding-interviews_2Fquestion-ranking]: https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=13&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking