206. Reverse Linked List

 

Reverse a singly linked list

 

206. Обернуть связный список

 

Оберните связный список

 

// C++

/**

 * 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) {

       

  }

};

 

// Java

/**

 * 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) {

       

  }

}

 

РЕШЕНИЕ

структуры данных - список

 

Анализ алгоритма

Построим второй (результирующий) список следующим образом. Изначально он пустой. Берем первый элемент исходного списка и вставляем его первым во второй список. Продолжаем этот процесс перестановки пока первый список не станет пустым. Таким образом первый список перевернется и его элементы перейдут во второй.

 

Начальное состояние входного head и выходного newhead списка:

 

Перебрасываем первый элемент первого списка в голову второго:

 

Еще раз перебросим первый элемент первого списка в голову второго:

 

Проведем еще одну итерацию переброски элемента:

 

Реализация алгоритма

 

class Solution

{

public:

  ListNode* reverseList(ListNode* head)

  {

    if (head == NULL) return head;

    ListNode *ptr, *newHead = head;

    head = head->next;

    newHead->next = NULL;

 

    while (head != NULL)

    {

      ptr = head->next;

      head->next = newHead;

      newHead = head;

      head = ptr;

    }

    return newHead;

  }

};

 

Java реализация

 

public class Solution

{

  public ListNode reverseList(ListNode head)

  {

    if (head == null) return head;

    ListNode ptr, newHead = head;

    head = head.next;

    newHead.next = null;

 

    while (head != null)

    {

      ptr = head.next;

      head.next = newHead;

      newHead = head;

      head = ptr;

    }

    return newHead;

  }

}