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;
}
}