GuoXin Li's Blog

ListNode-Data Structure

DataStructure
字数统计: 281阅读时长: 1 min
2021/08/07 Share

ListNode

递归反转

反转一个链表（用递归的方式）：

1
2
3
4
5
6
7
ListNode reverse(ListNode head){
  if(head.next == null) return head;
  ListNode last = reverse(head.next);
  head.next.next = head;
  head.next = null;
  return last;
}

关键的重点在于：ListNode last = reverse(head.next)，此句在于将 head 之后的链表进行反转，反转之后，head 仍然指向 head 之后的第一个节点，而 last 指向的是 head 之后所有链表的最后一个节点。

设原链表：1，2，3，4

即：head->next—>( 2， 3， 4 —> null )；

此时 head—>next—>next == 2

所以 head —> next—>next = head 即为 2 —> head ；

然后，head —>next = null 即将 head 变为最后一个节点，head 不应该再指向任何节点。

以上递归函数需要有 base case：

if(head.next == null) return head;

反转链表前 N 个节点

1
2
3
4
5
6
7
8
9
10
11
12
ListNode successor = null;

ListNode reverseNode(ListNode head, int n){
  if(n == 1){
    successor = head->next;
    return head;
  }
  ListNode last = reverseNode( head->next, n-1);
  head->next->next = head;
  head->next = successor;
  return last;
}

反转链表的一部分

1
2
3
4
5
6
7
8
ListNode reverseBetween(ListNode head, int m, int n){
  if(m==1){
    return reverseN(head, n);
  }
  head.next = reverseBetween(head.next, m-1, n-1);
  return head;
  
}
CATALOG
  1. 1. ListNode
    1. 1.0.1. 递归反转
Total : 89
2022
2021
2020
2019
2018
essay Deep Learning Paper-reading learning-note C++ CUDA cmake LeetCode DataStructure Numpy OS-Linux PAT slidingwindow git golang BuaaAssignments CG
Machine-Learning Data-Structure