算法: 翻转链表 206. Reverse Linked List

约定不等于承诺〃 2022-08-28 04:49 145阅读 0赞

# 206. Reverse Linked List #

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5p625p6E5biI5piT562L_size_16_color_FFFFFF_t_70_g_se_x_16]

Input: head = [1,2,3,4,5]
    Output: [5,4,3,2,1]

Example 2:  
![在这里插入图片描述][5c2915b14ac146aaa697395b8be673e0.png]

Input: head = [1,2]
    Output: [2,1]

Example 3:

Input: head = []
    Output: []

Constraints:

*  The number of nodes in the list is the range \[0, 5000\].
 *  \-5000 <= Node.val <= 5000

# 递归解法 #

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public ListNode reverseList(ListNode head) {
        
            return helper(head, null);
        }
    	private ListNode helper(ListNode newHead, ListNode head) {
        
    		if (newHead == null) return head;
    		ListNode next = newHead.next;
    		newHead.next = head;
    		return helper(next, newHead);
    	}
    }

# 遍历解法 #

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        public ListNode reverseList(ListNode head) {
        
            ListNode newHead = null;
    		while (head != null) {
        
    			ListNode next = head.next;
    			head.next = newHead;
    			newHead = head;
    			head = next;
    		}
    		return newHead;
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5p625p6E5biI5piT562L_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/23299a4fca674699b4323469118754a4.png
[5c2915b14ac146aaa697395b8be673e0.png]: /images/20220828/69f9daca624348ac9d0fcd1bc4719972.png