【力扣·图解算法数据结构 Day02】剑指 Offer 24. 反转链表

题目来源

题目链接如下：点击跳转

题目介绍

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例

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

限制

• 0 <= 节点个数 <= 5000

解题思路

• 思路一: 栈
  • 谈到反转，总是容易让人想到栈先进后出的特点
  • 使用栈反转链表，首先需要将链表遍历，按顺序存入栈中
  • 最后需要俩个节点存储下一个栈元素和当前栈元素，实现链表的反转
• 思路二: 递归
  • 同样让人容易想到的是递归，因为递归的特点有回退顺序是它调用顺序的逆序
  • 使用递归，我们需要想明白，递归出口怎么定义
  • 链表节点只有在两个的时候，才可以进行顺序的颠倒，所以递归到最后一个节点是不合理的
  • 不妨将条件设置为最后一个节点的前一个节点为出口，假设使用节点temp进行遍历，条件应为: temp.next.next == null; 这样就实现了将倒数第二个节点设为了出口
  • 实现反转的逻辑即为 倒数第一个节点指向倒数第二个节点，将原先倒数第二个节点指向倒数第一个节点的指向拆除

  •  temp.next.next = temp;
     temp.next = null;
    1
    2

  • 成功实现反转
• 思路三: 头插法
  • 插入链表节点的方法之一，特点就是插入的顺序相反
  • 思路即为重新创造一个新链表，循环遍历原链表，每循环一次，将该链表节点使用头插法插入新链表，最后返回新链表，成功实现链表的反转
• 思路四: 迭代
  • 链表的反转首先需要当前节点和上一个节点来反转，因为反转后，当前节点的下一个节点无法找到，所有还需要存储下一个节点，直到当前节点为空
  • 此时，当前节点的上一个节点即为反转链表的表头

代码实现

java

思路一

class Solution {
    public ListNode reverseList(ListNode head) {
        LinkedList<ListNode> stack = new LinkedList<ListNode>();
        while(head != null){
			stack.addLast(head);
			head = head.next;
		}
		ListNode cur = null;
		if(!stack.isEmpty()){
			cur = stack.removeLast();
			head = cur;
		}
		while(!stack.isEmpty()){
			ListNode next = stack.removeLast();
			cur.next = next;
			next.next = null;
			cur = next;
		}
		return head;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

思路二

class Solution {
    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;
    }
}
1
2
3
4
5
6
7
8
9
10
11

思路三

class Solution {
    public ListNode reverseList(ListNode head) {
		if(head==null){
			return head;
		}
		ListNode newLast  = head;
		ListNode cur = head.next;
		newLast.next = null;
		while(cur != null){
			ListNode temp  = cur.next;
			cur.next = newLast;
			newLast = cur;
			cur = temp;
		}
		return newLast;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

思路四

class Solution {
    public ListNode reverseList(ListNode head) {
		if(head == null){
			return head;
		}
		ListNode pre = null;
		while(head != null){
			ListNode next = head.next;
			head.next = pre;
			pre = head;
			head = next;
		}
		return pre;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

问题得以解决，如有更好思路欢迎评论，私聊。