• 如果您觉得本站非常有看点，那么赶紧使用Ctrl+D 收藏吧

# 《剑指Offer》24：反转链表

2周前 (11-19) 6次浏览

## 题目

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

## 放码

``````import java.util.LinkedList;

public class ReverseList {

//三指针操作
public ListNode reverse(ListNode head){

if(head == null) {
}

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;
}

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;//防止最后元素死循环而造成的OOM
p.next = temp;
p = p.next;
}

return result;
}

}
``````

## 测试

``````import static org.junit.Assert.*;

import org.junit.Test;

public class ReverseListTest {

@Test
public 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});

//---

raw = SinglyLinkedList.intArray2List(new int[] {1});
expected = SinglyLinkedList.intArray2List(new int[] {1});

//---

raw = SinglyLinkedList.intArray2List(new int[] {1, 2});
expected = SinglyLinkedList.intArray2List(new int[] {2, 1});

//---

assertNull(rl.reverse(null));

}

@Test
public 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});

//---

raw = SinglyLinkedList.intArray2List(new int[] {1});
expected = SinglyLinkedList.intArray2List(new int[] {1});

//---

raw = SinglyLinkedList.intArray2List(new int[] {1, 2});
expected = SinglyLinkedList.intArray2List(new int[] {2, 1});