題目

定義一個函數，輸入一個鏈表的頭節點，反轉鏈表并輸出反轉后鏈表的頭節點。鏈表節點定義如下：

public static class ListNode{public int val;public ListNode next;public ListNode(int val) {this.val = val;}
}

分析

方法一：使用三個指針進行邊移動邊逆。

方法二：利用棧先進后出的性質進行反轉鏈表。

放碼

import java.util.LinkedList;
import com.lun.util.SinglyLinkedList.ListNode;public class ReverseList {//三指針操作public ListNode reverse(ListNode head){if(head == null) {return head;}ListNode a = head;ListNode b = a.next;ListNode c = null;while(a != null) {//真正改變轉向a.next = c;//開始移位c = a;a = b;if(b != null)b = b.next;}return c;}//利用棧的先進后出性質public ListNode reverse2(ListNode head) {if(head == null) {return null;}LinkedList<ListNode> stack = new LinkedList<>();ListNode p = head;while( p != null) {stack.push(p);p = p.next;}ListNode result = stack.pop(), temp = null;;p = result;while(!stack.isEmpty()) {temp = stack.pop();temp.next = null;//防止最后元素死循環而造成的OOMp.next = temp;p = p.next;}return result;}}

測試

import static org.junit.Assert.*;import org.junit.Test;import com.lun.util.SinglyLinkedList;
import com.lun.util.SinglyLinkedList.ListNode;public class ReverseListTest {@Testpublic void testReverse() {ReverseList rl = new ReverseList();ListNode raw = SinglyLinkedList.intArray2List(new int[] {1, 2, 3, 4, 5, 6, 7});ListNode expected = SinglyLinkedList.intArray2List(new int[] {7, 6, 5, 4, 3, 2, 1});assertTrue(SinglyLinkedList.equals(rl.reverse(raw), expected));//---raw = SinglyLinkedList.intArray2List(new int[] {1});expected = SinglyLinkedList.intArray2List(new int[] {1});assertTrue(SinglyLinkedList.equals(rl.reverse(raw), expected));//---raw = SinglyLinkedList.intArray2List(new int[] {1, 2});expected = SinglyLinkedList.intArray2List(new int[] {2, 1});assertTrue(SinglyLinkedList.equals(rl.reverse(raw), expected));//---assertNull(rl.reverse(null));}@Testpublic void testReverse2() {ReverseList rl = new ReverseList();ListNode raw = SinglyLinkedList.intArray2List(new int[] {1, 2, 3, 4, 5, 6, 7});ListNode expected = SinglyLinkedList.intArray2List(new int[] {7, 6, 5, 4, 3, 2, 1});//System.out.println(SinglyLinkedList.print(rl.reverse2(raw)));assertTrue(SinglyLinkedList.equals(rl.reverse2(raw), expected));//---raw = SinglyLinkedList.intArray2List(new int[] {1});expected = SinglyLinkedList.intArray2List(new int[] {1});assertTrue(SinglyLinkedList.equals(rl.reverse2(raw), expected));//---raw = SinglyLinkedList.intArray2List(new int[] {1, 2});expected = SinglyLinkedList.intArray2List(new int[] {2, 1});assertTrue(SinglyLinkedList.equals(rl.reverse2(raw), expected));//---assertNull(rl.reverse2(null));}}