Reverse a singly linked list.

 

思路：

正常情况下需要转置的链表一般都会做成双链表以减小转置的开销，但是题目规定是单链表。因此想到的方法是通过额外的引用指向节点，并且申请新引用存放转置时候的next数据域，来达到转置单链表的目的。迭代法比较繁琐，应该考虑到每一步的顺序，否则就会丢失引用。而Stack类的话相当直观，就是将整个链表放入栈内存取，即完成了倒置。

 

解法：

1.迭代法

循环中四步依次为存放当前节点的后节点，将当前结点的next指向前节点，将代表前节点的引用移动至当前节点，将代表当前节点的引用移动至下一个节点。顺序不可打乱。

1 /* 2     public class ListNode 3     { 4         int val; 5         ListNode next; 6  7         ListNode(int x) 8         { 9             val = x;10         }11     }12 */13 14 public class Solution15 {16     public ListNode reverseList(ListNode head)17     {18         if(head == null || head.next == null)19             return head;20         21         ListNode backPointer = head;22         ListNode pointer = head.next;23 24         backPointer.next = null;25 26         ListNode addition;27 28         while(pointer != null)29         {30             addition = pointer.next;31             pointer.next = backPointer;32             backPointer = pointer;33             pointer = addition;34         }35 36         return backPointer;37     }38 }

 

2.Stack类法

1 /* 2     public class ListNode 3     { 4         int val; 5         ListNode next; 6  7         ListNode(int x) 8         { 9             val = x;10         }11     }12 */13 14 import java.util.Stack;15 16 public class Solution17 {18     public ListNode reverseList(ListNode head)19     {20         if(head == null || head.next == null)21             return head;22 23         Stack
     
       stack = new Stack<>();24         ListNode temp = head;25         while(temp != null)26         {27             stack.push(temp);28             temp = temp.next;29         }30 31         head = stack.pop();32         temp = head;33 34         while(!stack.isEmpty())35         {36             temp.next = stack.pop();37             temp = temp.next;38         }39 40         temp.next = null;41         return head;42     }43 }