-
Notifications
You must be signed in to change notification settings - Fork 2
/
ReverseList.java
118 lines (110 loc) · 1.98 KB
/
ReverseList.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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
package list;
/**
* 链表反转
* @author kesar
*
*/
public class ReverseList
{
/**
* 递归
* @param head
* @return
*/
public static ListNode reverseList1(ListNode head)
{
if(head==null)
{
return null;
}
ListNode parent=head.next;
if(parent==null)
{
return head;
}
head.next=null;
return reverseList1(head,parent);
}
/**
* 递归,绑定父子节点关系
* @param child
* @param parent
* @return
*/
private static ListNode reverseList1(ListNode child,ListNode parent)
{
if(parent==null)
{
return child;
}
ListNode last=parent.next;
parent.next=child;
return reverseList1(parent, last);
}
/**
* 反转链表,返回新的头节点
* @param head
* @return
*/
public static ListNode reverseList(ListNode head)
{
if(head==null)
{
return null;
}
ListNode pChild=head;
ListNode pParent=pChild.next;
ListNode pLast=null;
pChild.next=null;
while (pParent!=null)
{
// 绑定关系
pLast=pParent.next;
pParent.next=pChild;
// 设定关系
pChild=pParent;
pParent=pLast;
}
return pChild;
}
/**
* 链表倒序打印输出
* @param head
*/
public static void reversePrintList(ListNode head)
{
if (head == null)
{
return;
}
reversePrintList(head.next);
System.out.println(head.value+" ");
}
/**
* @param args
*/
public static void main(String[] args)
{
//reversePrintList(new ListNode(0, new ListNode(1, new ListNode(2, new ListNode(3)))));
System.out.println(reverseList1(new ListNode(0, new ListNode(1))));
}
private static class ListNode
{
int value;
ListNode next;
public ListNode(int value)
{
this.value = value;
}
public ListNode(int value, ListNode next)
{
this.value = value;
this.next = next;
}
@Override
public String toString()
{
return "ListNode [value=" + value + ", next=" + next + "]";
}
}
}