Topic describes

Define a function that takes the head node of a linked list, reverses the list, and outputs the head node of the reversed list.

Example:

Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULLCopy the code

Limitations:

  • 0 <= Number of nodes <= 5000

solution

Define Pointers pre, cur to null and the head node, respectively.

Iterate through the list, temporarily save cur.next to T, and then redirect the pointer to the node to which the pointer to cur points to the node to which the pointer to pre points, cur.next = pre. And then the pre pointer points to cur, and the cur pointer goes forward.

When the traversal is complete, return the pre pointer.

Python3

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre, cur = None, head
        while cur:
            t = cur.next
            cur.next = pre
            pre = cur
            cur = t
        return pre
Copy the code

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode t = cur.next;
            cur.next = pre;
            pre = cur;
            cur = t;
        }
        return pre;
    }
}
Copy the code

JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  let node = head;
  let pre = null;
  while (node) {
    let cur = node;
    node = cur.next;
    cur.next = pre;
    pre = cur;
  }
  return pre;
};
Copy the code

C++

Class Solution {public: ListNode* reverseList(ListNode* head) {// ListNode* first = new ListNode(-1); // ListNode *p = head, *q; // while (p) { // q = p->next; // p->next = first->next; // first->next = p; // p = q; // } // return first->next; // ListNode *pre = NULL, *cur = head; while (cur) { ListNode* temp = cur->next; cur->next = pre; pre = cur; cur = temp; } return pre; }};Copy the code