从尾到头打印链表

题目描述

反转链表，返回反转后链表头部

Input: 1->2->3

Output: 3->2->1

思路

class Node{
    int val;
    Node next;
}

• 递归

  public Node reverseList(Node head){
      if(head==null || head.next==null)//如果没有节点或者只有一个节点直接返回
          return head;
      Node cur = head.next;//保存当前节点的下一个节点
      head.next = null;//打断当前节点的指针域，使之能够成为末尾节点
      Node newHead = reverseList(cur); //返回以pNext为头的反转链表，
      								//返回之后newHead为新头，pNext为末节点
      cur.next = head;//在以newHead为头、以pNext为末的新链表中接上应该为末节点的head
      return newHead;
  }

• 栈

  public Node reverseList(Node head){
      if(head==null || head.next==null)
          return head;
      Stack<Node> s = new Stack<>();
      Node newHead = null;//记录最后一个指针,即反转后头节点
      while(head.next!=null){//最后一个指针不入栈，方便出栈容易实现
          s.push(head);
          head = head.next;
      }
      newHead = head;
      while(!s.isEmpty()){
          head.next = s.pop();
          head = head.next;
      }
      head.next = null;
      return newHead;
  }

• 遍历

  public Node reverseList(Node head){
      Node newHead = null;//反转后的新头节点
      Node cur = head; //当前节点
      Node pre = null; //当前节点前一节点
      while(node!=null){
          Node next = cur.next; //当前节点后一节点
          if(next==null)
              newHead = cur;
          cur.next = pre;//当前节点下一节点指向前节点，起到反转作用
          pre = cur;
          cur = next;//三个指针整体向后移动，起到遍历效果
      }
  }

拓展

反转部分链表，反转[m,n]之间的链表

Input: 1->2->3->4->5->6 [2,5]

Output: 1->5->4->3->2->6

个人感觉递归实现困难，采用栈和遍历的方式应该简单（只要记录以下入栈节点个数或者遍历个数即可）