LeetCode-206反转链表

反转一个单链表。

示例:

1
2
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?

迭代解法:

将第一个节点的下一个节点移动到头部,直到第一个节点成为最后一个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode newHead = head;

while(head.next != null){
ListNode temp = head.next;
head.next = head.next.next;
temp.next = newHead;
newHead = temp;
}
return newHead;
}
迭代解法2:

使用一个空节点作为新链表,将当前链表中的数据一个一个的添加到新链表的头部

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode newHead = null;
Node temp = node;
while(temp != null){
ListNode next = temp.next;

temp.next = newHead;
newHead = temp;

temp = next;
}
return newHead;
}
递归解法:

递归,直到最后一个节点才开始处理,将相邻的两个节点的指向反转,然后返回最后一个节点作为头结点。

1
2
3
4
5
6
7
8
9
public ListNode reverseList(ListNode head) {
if(head ==null || head.next == null){
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×