单向链表反转

题目出处

• Leetcode 206. 反转链表
• 剑指 Offer - 24 - 反转链表
• 面试实际遇到过

单向链表反转

1 题目描述

实现单向链表反转 例如：a->b->c->d 反转之后 d->c->b->a； 链表长度不定

class Node {
  public int  value;
  public Node next;
}

2 解题思路

2.1 递归

递归，效率低

public Node reverseLinkList(Node head) {
  if(null == head || null == head.next){
    return head;
  }else{
    Node next = head.next;
    Node newHead = reverseLinkList(next);
    next.next = head;
    head.next = null;
    return newHead;
  }
}

2.2 迭代

循环，两两交换

public Node reverseLinkList(Node head) {
  if(null == head || null == head.next){
    return head;
  }else{
    //first 和 second 分别指向原来的第一、第二节点
    Node first = head;
    Node second = head.next;
    
    Node temp = null;
    while(null != second){
      //将原来的第三节点临时存在 temp
      temp = second.next;
      //原来的第二节点指向原来的第一节点
      second.next = first;
      //first 后移，指向原来的第二节点
      first = second;
      //second 后移，指向原来的第三节点
      second = temp;
      //若原来第三节点不为空，则继续两两交换，并后移
    }
    
    //将原来的头节点指向null
    head.next = null;
    
    return first;
  }
}

2.3 头插法

public ListNode reverseList(Node head) {
    Node newHead = new Node(-1);
    while (head != null) {
        Node next = head.next;
        head.next = newHead.next;
        newHead.next = head;
        head = next;
    }
    return newHead.next;
}