关于链表的反转

引用

LeetCode 206.反转链表

正文 递归实现（运行77ms解决，效率极差） 使用分治法的思想，拿到一个链表1-2-3-4-5，当你要反转这个链表的时候，你只需要得到2-3-4-5的反转，再加上1就可以了，同理2-3-4-5的反转就是将2-3-4反转，再结尾加上2便可。以此类推直到链表只剩下5，那5的反转就是自己本身再依次递归回去。/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { if (head == null) return null; if (head.next == null) return head; else { ListNode node = reverseList(head.next); ListNode t = node; while (t.next != null) t = t.next; t.next = head; head.next = null; return node; } } } 使用栈（运行4ms，效率差） 使用栈暂存所有节点然后依次重新连接。/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { if (head == null) return null; Stack<ListNode> stack = new Stack<>(); ListNode t = head; while (t != null) { stack.push(t); t = t.next; } ListNode first = stack.pop(); first.next = null; ListNode p = new ListNode(first.val); head = p; while (!stack.empty()) { ListNode a = stack.pop(); a.next = null; p.next = a; p = p.next; } return head; } } 迭代（运行不足1ms，效率高） 从链表的首个位置取出元素指向新的链表，直到原链表不再拥有元素。/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { if (head == null) return null; ListNode t = head; ListNode newList = null; ListNode p = head; while (t != null) { p = t.next; t.next = newList; newList = t; t = p; } return newList; } }

转载于:https://www.cnblogs.com/ysxiiun/p/10113800.html

相关资源：java链表反转及排序