206. 反转链表

leetcode链接：
https://leetcode.cn/problems/reverse-linked-list/

方案一

思路： 将链表的每个元素通过循环的方式放入到List的数组中，然后将List数组从前往后遍历，形成一个新的数组。

注：
1、输入的链表为null时，需要特殊判断
2、tempNode.next = null;是必要的，如果将最后一个赋值为null，其将不会是一个单链表，将会形成一个环形链表

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return head;
        }

        ListNode tempNode = head;
        
        List<ListNode> tempList = new ArrayList<>();

        int i = 0;
        while (tempNode != null) {
            tempList.add(i, tempNode);
            i++;
            tempNode = tempNode.next;
        }

        tempNode = tempList.get(tempList.size() - 1);
        head = tempNode;
        for (int j = tempList.size() - 2 ; j >= 0; j--) {
            tempNode.next = tempList.get(j);
            tempNode = tempNode.next;
        }
        tempNode.next = null;

        return head;
    }
}

Accepted

• 28/28 cases passed (0 ms)
• Your runtime beats 100 % of java submissions
• Your memory usage beats 92.87 % of java submissions (40.2 MB)

分析

时间复杂度：
O( 2 n ) —-> O( n )

空间复杂度：
O( n )

方案二–双指针

参考链接：
https://leetcode.cn/problems/reverse-linked-list/solution/fan-zhuan-lian-biao-shuang-zhi-zhen-di-gui-yao-mo-/

双指针法

代码及其精炼，非常漂亮

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode right = head;
        ListNode left = null;
        ListNode temp = null;

        while(right != null) {
            temp = right;
            right = right.next;
            temp.next = left;
            left = temp;
        }

        return left;
    }
}

Accepted

• 28/28 cases passed (0 ms)
• Your runtime beats 100 % of java submissions
• Your memory usage beats 99.17 % of java submissions (39.9 MB)

分析

时间复杂度：
O( n )

空间复杂度：
O( 1 )

方案三–迭代

参考链接：
https://leetcode.cn/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/

class Solution {
	public ListNode reverseList(ListNode head) {
		//递归终止条件是当前为空，或者下一个节点为空
		if(head==null || head.next==null) {
			return head;
		}
		//这里的cur就是最后一个节点
		ListNode cur = reverseList(head.next);
		//这里请配合动画演示理解
		//如果链表是 1->2->3->4->5，那么此时的cur就是5
		//而head是4，head的下一个是5，下下一个是空
		//所以head.next.next 就是5->4
		head.next.next = head;
		//防止链表循环，需要将head.next设置为空
		head.next = null;
		//每层递归函数都返回cur，也就是最后一个节点
		return cur;
	}
}

作者：wang_ni_ma
链接：https://leetcode.cn/problems/reverse-linked-list/solution/dong-hua-yan-shi-206-fan-zhuan-lian-biao-by-user74/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。