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

《剑指Offer》24:反转链表

互联网 diligentman 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;
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;//防止最后元素死循环而造成的OOM
			p.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 {

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

}

喜欢 (0)