反转链表

参考视频地址

视频地址

非递归实现

过程描述

需要两个指针prev, head在链表中进行移动；另外还需要一个指针save,用来保存head节点的下一个节点

举例说明

初始化的时候

• prev 1(head)->2->3->4->null
  • prev = null
  • head = 1
  • save = null

第一次循环

改变指针的指向

• prev<-1(head) 2->3->4->null
  • prev = null
  • head = 1
  • save = 2

往右平移prev,head

• null<-1(prev) 2(head)->3->4->null
  • prev = 1
  • head = 2
  • save = 2

第二次循环

改变指针指向

• null<-1(prev)<-2(head) 3->4->null
  • prev = 1
  • head = 2
  • save = 3

往右平移指针prev,head

• null<-1<-2(prev) 3(head)->4->null
  • prev = 2
  • head = 3
  • save = 3

第三次循环

改变指针指向

• null<-1<-2(prev)<-3(head) 4->null
  • prev = 2
  • head = 3
  • save = 4

往右平移指针prev,head

• null<-1<-2<-3(prev) 4(head)->null
  • prev = 3
  • head = 4
  • save = 4

第四次循环

改变指针指向

• null<-1<-2<-3(prev)<-4(head) null
  • prev = 3
  • head = 4
  • save = null

往右平移指针prev,head

• null<-1<-2<-3<-4(prev) null(head)
  • prev = 4
  • head = null
  • save = null

循环结束条件

根据第四次循环的结果，可以看到循环的终止条件就是head=null

最后返回的头部

prev就是反转后链表的头部

javascript代码实现

let reverseList = function(head){
  let prev = null;
  while(head){
    // 改变指向
    let save = head.next;
    head.next = prev;
    // 向右平移prev和head指针
    prev = head;
    head = save;
  }
  return prev;
}

python实现

def reverseList(head):
  prev = None
  while(head):
    # 改变指向
    save = head.next
    head.next = prev
    # 向右平移prev和head指针
    prev = head
    head = save
  return prev

c++实现

ListNode* reverseList(ListNode* head){
  
}

递归实现

def reverseList(head):
  if head == None or head.next == None:
    return head
  let new_head = reverseList(head.next)
  head.next.next = head
  head.next = null
  return new_head