[LeetCode] 206. Reverse Linked List

轉自LeetCode

Reverse a singly linked list.

<Solution>

題目很單純，就是要反轉 single linked list

畫個圖會比較容易解

code 如下
c++

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* reverseList(ListNode* head) {
	if(!head || !head->next) {
	return head;
	}
	ListNode *tail = head;
	ListNode *dummy = new ListNode(-1);
	dummy->next = head;
	while(tail->next) {
	ListNode *newHead = tail->next;
	tail->next = newHead->next;
	//> current head becomes the next node of new head
	newHead->next = dummy->next;
	//> dummy->next always points to head
	dummy->next = newHead;
	}
	return dummy->next;
	}
	};

view raw reverseSingleLinkedList.cpp hosted with ❤ by GitHub

還有更簡潔的寫法

code 如下
c++

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* reverseList(ListNode* head) {
	ListNode *newHead = NULL;
	while(head) {
	ListNode *nextNode = head->next;
	head->next = newHead;
	newHead = head;
	head = nextNode;
	}
	return newHead;
	}
	};

view raw reverseSingleLinkedList_2.cpp hosted with ❤ by GitHub

kotlin

	/**
	* Example:
	* var li = ListNode(5)
	* var v = li.`val`
	* Definition for singly-linked list.
	* class ListNode(var `val`: Int) {
	* var next: ListNode? = null
	* }
	*/
	class Solution {
	fun reverseList(head: ListNode?): ListNode? {
	var currHead = head
	var newHead: ListNode? = null
	var nextHead: ListNode?
	while(currHead != null) {
	nextHead = currHead!!.next
	currHead.next = newHead
	newHead = currHead
	currHead = nextHead
	}
	return newHead
	}
	}

view raw reverse_linked_list.kt hosted with ❤ by GitHub

Recursive 的寫法
Java

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

view raw reverseSingleLinkedList_3.java hosted with ❤ by GitHub

kotlin

	/**
	* Example:
	* var li = ListNode(5)
	* var v = li.`val`
	* Definition for singly-linked list.
	* class ListNode(var `val`: Int) {
	* var next: ListNode? = null
	* }
	*/
	class Solution {
	fun reverseList(head: ListNode?): ListNode? {
	return reverse(head, null)
	}
	fun reverse(head: ListNode?, newHead: ListNode?): ListNode? {
	if (head == null) {
	return newHead
	}
	val nextHead = head?.next
	head.next = newHead
	return reverse(nextHead, head)
	}
	}

view raw reverse_linked_list.kt hosted with ❤ by GitHub