链表及其反转的JAVA实现

Posted on Edited on In

链表的JAVA实现

在JAVA中，JAVA的集合(collection)实现了各种常用的数据结构，包括链表。

下面自己来实现简单的单链表。链表是由一个个的相互连接的结点组成，结点又由数据域和指针域组成，指针域指向下一个结点。

1
2
3
┌───┬───┐   ┌───┬───┐   ┌───┬───┐   ┌───┬───┐
│ A │ ●─┼──>│ B │ ●─┼──>│ C │ ●─┼──>│ D │   │
└───┴───┘   └───┴───┘   └───┴───┘   └───┴───┘

JAVA没有struct结构体，所以用一个Node Class表示结点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 结点
public class ListNode<E>{
	// 数据域
	private E data;
	// 指针域
	private ListNode<E> next = null;
	
	// 构造函数
	public ListNode(E data) {
		this.data = data;
	}
	// 构造函数
	public ListNode(E data, ListNode<E> next) {
        this.data = data;
        this.next=next;
    }
	
	public void setData(E data) {
		this.data = data;
	}
	
	public E getData() {
		return this.data;
	}
	
	public void setNext(ListNode<E> next) {
		this.next = next;
	}
	
	public ListNode<E> getNext() {
		return this.next;
	}
}

链表反转

面试题5 - 从尾到头打印链表并不算是真正的链表反转，它只是将链表中的元素放进到新的数组对象中去了。

对于链表的反转问题，可以新建链表及节点关系；也可以在原有列表的基础上进行指针的变换，这样考察点就在于指针的运用（pointer manipulation）。这里主要阐述在原有列表的基础上进行指针的变换的方法。

迭代法（Iterative）

迭代法是从前向后顺序地交换两个节点的相对位置。

我们需要三个指针：

  • pre pointer：存储上一个节点，因为是单链表，在迭代过程中，当链表头移动到下一个结点后，就无法访问上一个结点了。
  • cur pointer：指示我们当前的指向。
  • next pointer：当我们改变当前结点指向后，我们就会丢失原来的下一个结点，所以需要一个结点来储存，才能知道我们的下一次迭代的前进方向。

最后的结果（图片来自视频）

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 static ListNode<Integer> LinkedListReverse1(ListNode<Integer> listNode) {
    if (listNode == null) {
        return listNode;
    }
    // 用于存储上一结点
    ListNode<Integer> pre = null;
    // 指向当前结点
    ListNode<Integer> cur = listNode;
    // 临时结点，用于保存当前结点的指针域（即下一结点），以知道迭代进行的方向
    ListNode<Integer> next = new ListNode<>(null);
    while (cur != null) {// 当前结点为null，说明位于尾结点
        // 存储下一节点
        next = cur.getNext();
        // 反转指针域的指向（指向前一节点）
        cur.setNext(pre);
        // 将本次迭代的当前节点，作为下次循环的前结点
        pre = cur;
        // 将存储的下一节点取出，作为下一次迭代的当前节点
        cur = next;
    }
    // 还回新链表的头结点，即原链表的尾结点
    return pre;
}

Time: O(n)
Space: O(1)

递归法（Recursive）

递归法是从后向前逆序地交换两c个节点的相对位置。递归即是借助了系统的”栈”。

每一次迭代就像是向另一个人发出了命令：将我（本节点，本此迭代的head）后面的所有结点反转，不包括我。

每一次迭代，我们有的资源是返回的反转后的剩下链表（rlh，reversed list head）以及本节点（head）；每一次迭代，执行的动作是，将rlh指向我自己，再将新的rlh返回到上一次迭代。

图片来自视频

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 递归法
public static ListNode<Integer> LinkedListReverse2(ListNode<Integer> listNode) {
	// base case
	if (listNode == null || listNode.getNext() == null) {
			return listNode;// 若为空链或者当前结点在尾结点，则直接还回
		}
	// 先反转后续节点listNode.getNext()
	ListNode<Integer> reHead = LinkedListReverse2(listNode.getNext());
	// 执行本次递归的指向更改
	// S1：让下一节点指向本结点
	listNode.getNext().setNext(listNode);
	// S2：断开本节点的指向，因为在本此迭代结束后，本次的本节点应该为尾节点作为下一次迭代的“下一节点”
	listNode.setNext(null);
	// 反转后新链表的头结点
	return reHead;
   }

Time: O(n)
Space: O(n)

代码

ListNode.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
public class Main {
	public static void main(String[] args) {
		ListNode<Integer> node0 = new ListNode<>(0);
		ListNode<Integer> node1 = new ListNode<>(1);
		ListNode<Integer> node2 = new ListNode<>(2);
		ListNode<Integer> node3 = new ListNode<>(3);
		node0.setNext(node1);
		node1.setNext(node2);
		node2.setNext(node3);
		
		ListNode<Integer> h1 = node0;
		System.out.println("反转前的链表：");
		while (h1 != null) {
			System.out.println(h1.getData());
			h1 = h1.getNext();
		}
		
		node0 = LinkedListReverse1(node0);
//		node0 = LinkedListReverse2(node0);
		
		ListNode<Integer> h2 = node0;
		System.out.println("反转后的链表：");
		while (h2 != null) {
			System.out.println(h2.getData());
			h2 = h2.getNext();
		}
		
	}
	
	// 迭代法
	public static ListNode<Integer> LinkedListReverse1(ListNode<Integer> listNode) {
		if (listNode == null) {
			return listNode;
		}
		// 用于存储上一结点
		ListNode<Integer> pre = null;
		// 指向当前结点
		ListNode<Integer> cur = listNode;
		// 临时结点，用于保存当前结点的指针域（即下一结点），以知道迭代进行的方向
		ListNode<Integer> next = new ListNode<>(null);
		while (cur != null) {// 当前结点为null，说明位于尾结点
			// 存储下一节点
			next = cur.getNext();
			// 反转指针域的指向（指向前一节点）
			cur.setNext(pre);
			// 将本次迭代的当前节点，作为下次循环的前结点
			pre = cur;
			// 将存储的下一节点取出，作为下一次迭代的当前节点
			cur = next;
		}
		// 还回新链表的头结点，即原链表的尾结点
		return pre;
    }

	
	// 递归法
	public static ListNode<Integer> LinkedListReverse2(ListNode<Integer> listNode) {
		// base case
		if (listNode == null || listNode.getNext() == null) {
				return listNode;// 若为空链或者当前结点在尾结点，则直接还回
			}
		// 先反转后续节点listNode.getNext()
		ListNode<Integer> reHead = LinkedListReverse2(listNode.getNext());
		// 执行本次递归的指向更改
		// S1：让下一节点指向本结点
		listNode.getNext().setNext(listNode);
		// S2：断开本节点的指向，因为在本此迭代结束后，本次的本节点应该为尾节点作为下一次迭代的“下一节点”
		listNode.setNext(null);
		// 反转后新链表的头结点
		return reHead;
    }

	
}

Main.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
public class Main {
	public static void main(String[] args) {
		ListNode<Integer> node0 = new ListNode<>(0);
		ListNode<Integer> node1 = new ListNode<>(1);
		ListNode<Integer> node2 = new ListNode<>(2);
		ListNode<Integer> node3 = new ListNode<>(3);
		node0.setNext(node1);
		node1.setNext(node2);
		node2.setNext(node3);
		
		ListNode<Integer> h1 = node0;
		System.out.println("反转前的链表：");
		while (h1 != null) {
			System.out.println(h1.getData());
			h1 = h1.getNext();
		}
		
		node0 = LinkedListReverse1(node0);
//		node0 = LinkedListReverse2(node0);
		
		ListNode<Integer> h2 = node0;
		System.out.println("反转后的链表：");
		while (h2 != null) {
			System.out.println(h2.getData());
			h2 = h2.getNext();
		}
		
	}
	
	// 迭代法
	public static ListNode<Integer> LinkedListReverse1(ListNode<Integer> listNode) {
		if (listNode == null) {
			return listNode;
		}
		// 用于存储上一结点
		ListNode<Integer> pre = null;
		// 指向当前结点
		ListNode<Integer> cur = listNode;
		// 临时结点，用于保存当前结点的指针域（即下一结点），以知道迭代进行的方向
		ListNode<Integer> next = new ListNode<>(null);
		while (cur != null) {// 当前结点为null，说明位于尾结点
			// 存储下一节点
			next = cur.getNext();
			// 反转指针域的指向（指向前一节点）
			cur.setNext(pre);
			// 将本次迭代的当前节点，作为下次循环的前结点
			pre = cur;
			// 将存储的下一节点取出，作为下一次迭代的当前节点
			cur = next;
		}
		// 还回新链表的头结点，即原链表的尾结点
		return pre;
    }

	
	// 递归法
	public static ListNode<Integer> LinkedListReverse2(ListNode<Integer> listNode) {
		// base case
		if (listNode == null || listNode.getNext() == null) {
				return listNode;// 若为空链或者当前结点在尾结点，则直接还回
			}
		// 先反转后续节点listNode.getNext()
		ListNode<Integer> reHead = LinkedListReverse2(listNode.getNext());
		// 执行本次递归的指向更改
		// S1：让下一节点指向本结点
		listNode.getNext().setNext(listNode);
		// S2：断开本节点的指向，因为在本此迭代结束后，本次的本节点应该为尾节点作为下一次迭代的“下一节点”
		listNode.setNext(null);
		// 反转后新链表的头结点
		return reHead;
    }

	
}

References

一篇文章搞定面试中的链表题目(java实现)

Java单链表反转 详细过程

【LeetCode算法题详解】链表反转（已添加字幕）