leetcode 206. Reverse Linked List 反转字符串

布满荆棘的人生 2022-06-08 09:14 117阅读 0赞

Reverse a singly linked list.

反转链表，我这里是采用头插法来实现反转链表。

代码如下：

/*class ListNode
    {
          int val;
          ListNode next;
          ListNode(int x) { val = x; }
    }
    */
    public class Solution
    { 
      public ListNode reverseList(ListNode head)
        {
            if(head==null || head.next==null)
                return head;
    
            ListNode newHead=new ListNode(0);
            newHead.next=head;
            ListNode start=newHead.next;
    
            while(start.next!=null)
            {
                ListNode then=start.next;
                start.next=then.next;
                then.next=newHead.next;
                newHead.next=then;
            }
            return newHead.next;    
        }    
    }

下面是C++的做法，就是使用头部插入法来实现链表反转

代码如下：

#include <iostream>
    #include <vector>
    #include <string>
    #include <map>
    #include <set>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <algorithm>
    
    using namespace std;
    
    
    /*
    struct ListNode 
    {
         int val;
         ListNode *next;
         ListNode(int x) : val(x), next(NULL) {}
    };
    */
    
    class Solution 
    {
    public:
        ListNode* reverseList(ListNode* h) 
        {
            if (h == NULL || h->next == NULL)
                return h;
    
            ListNode* head = new ListNode(-1);
            head->next = h;
    
            ListNode* i = h->next;
            ListNode* fa = h;
            while (i != NULL)
            {
                fa->next = i->next;
                ListNode* tmp = i;
                i = i->next;
                tmp->next = head->next;
                head->next = tmp;
            }
            return head->next;
        }
    };