206. Reverse Linked List

Reverse a singly linked list.

 

解题思路：

求一个链表的逆序。一种方法是遍历链表，将节点保存到stack中，在一个个出栈加到链表中；另一个方法是遍历链表，将每个节点插入到队首。。

 

C++ 8ms

/**  * Definition for singly-linked list.  * struct ListNode {  *     int val;  *     ListNode *next;  *     ListNode(int x) : val(x), next(NULL) {}  * };  */ class Solution { public:     ListNode* reverseList(ListNode* head) {         if(head==NULL)return head;         ListNode* root=new ListNode(0);         ListNode* p=head;         while(p!=NULL){             ListNode*q=p->next;             p->next=root->next;             root->next=p;             p=q;         }         return root->next;     } };

 

Java 0ms

/**  * Definition for singly-linked list.  * public class ListNode {  *     int val;  *     ListNode next;  *     ListNode(int x) { val = x; }  * }  */ public class Solution {    public ListNode reverseList(ListNode head) {         if(head==null)return head;         ListNode p=head;         ListNode root=new ListNode(0);         while(p!=null){             ListNode q=p.next;             p.next=root.next;             root.next=p;             p=q;         }         return root.next;     } }

 

3ms

public class Solution {    public ListNode reverseList(ListNode head) {         if(head==null)return head;         Stack<Integer>stack=new Stack<Integer>();         ListNode p=head;         while(p!=null){             stack.push(p.val);             p=p.next;         }         p=head;         while(p!=null){             p.val=stack.pop();             p=p.next;         }         return head;     } }