[Leetcode] Reverse Linked List

Problem 

Reverse a singly linked list.

Analysis

• 这道题就是要把相邻两个node的指针指向反一反，反的过程当中要keep track of next node，不然这时候 node.next 变成前一个节点了
• 所以我们采用两个指针，prev 和 curr 来记录相邻的两个节点
• 反之前，先记录 curr.next, 即 tmp = curr.next 
• 然后可以反了，curr.next = prev
• 然后把prev 和 curr往右移，继续去处理还没反的nodes
• prev = curr
• curr = tmp
• Time: O(n)
• Space: O(1)

Code

	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) { val = x; }
	* }
	*/
	public class Solution {
	public ListNode reverseList(ListNode head) {
	if(head==null || head.next==null) return head;
	//use two nodes to keep track of two nodes
	ListNode prev = head;
	ListNode curr = head.next;
	while(curr!=null){
	//keep track of next node of curr, since we are going to change its next to prev
	ListNode tmp = curr.next;
	//reverse
	curr.next = prev;
	//shift right by one position
	prev = curr;
	curr = tmp;
	}
	//set tail
	head.next = null;
	return prev;
	}
	}

view raw reverse-linked-list.java hosted with ❤ by GitHub