链表——反转单向和双向链表

Posted on | In ,

题目：反转单向链表，函数返回新链表的头节点。

实现：
方法一：最简单的就是使用栈，但复杂度为O(N)。

方法二：在原来链表上进行操作，使复杂度为O(1)。
next = head.next;
主要搞清楚指针（链接）和实际值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class ReverseList {
	/**
	 * 反转单向链表
	 * 1. 保存当前头结点的下个节点。
	 * 2. 将当前头结点的下一个节点指向“上一个节点”，这一步是实现了反转。
	 * 3. 将当前头结点设置为“上一个节点”。
	 * 4. 将保存的下一个节点设置为头结点。
	 * @param head 链表表头
	 * @return 新表头
	 */
	public static Node reverseList1(Node head) {
		if (head == null || head.next == null) {
			return head;
		}
		Node pre = null;
		Node next = null;
		while (head != null) {
			next = head.next; //将head.next的值赋给next，即next保存第2个节点
			head.next = pre; //将pre的值赋给head.next，即将节点1指向为pre（空）节点
			pre = head; //将head的值赋给pre, 即将节点1设为“上一个节点”
			head = next; //将next的值赋给head，即将节点2设为“头节点”
		}
		return pre; //返回头节点
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
	/**
	 * 反转双向链表，大体上就是将next指针和previous指针名交换
	 * @param head
	 * @return
	 */
	public static DoubleNode reverseList2(DoubleNode head) {
		DoubleNode pre = null; 
		DoubleNode next = null;
		while (head != null) {
			next = head.next;
			head.next = pre;
			head.previous = next;
			pre = head;
			head = next;
		}
		return pre;
	}
}