GuilinDev

Lc0206

05 August 2008

206 - Reverse Linked List

原题概述

Reverse a singly linked list.

Example:

1
2

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

题意和分析

翻转一个单向链表，用递归和迭代的办法各实现一下。递归的办法；迭代的办法就是遍历每个结点然后把该节点的赋值为之前链表结点的next，然后把该结点的next赋值为之前链表的结点即可。

Time：都是O(n)；Space：递归是O(n)，迭代是O(1)。

这是线性表（ZHAO, QIAN, SUN, LI, ZHOU, WU, ZHENG, WANG）的逻辑状态。头指针指示链表中第一个结点（即第一个数据元素的存储映像）的存储位置。同时，由于最后一个数据元素没有直接后继，则线性链表中最后一个结点的指针为“空”（NULL）。

有时在单链表的第一个结点之前附设一个结点，称之为头结点。头结点的数据域可以不存储任何信息，也可以存储如线性表长度等类的附加信息，头结点的指针域存储指向第一个结点的指针（即第一个元素结点的存储位置）。此时，单链表的头指针指向头结点。若线性表为空，则头结点的指针域为“空”。

(http://www.cnblogs.com/keeya/p/9218352.html)

    • 遍历法就是在链表遍历的过程中将指针顺序置换
      enter image description here
      先上代码：

    1
2
3
4
5
6
7
8
9
10
11

    public static Node reverseList(Node node) {
  Node pre = null;
  Node next = null;
  while (node != null) {
      next = node.next;
      node.next = pre;
      pre = node;
      node = next;
  }
  return pre;
}

    依旧是1->2->3->4

  • 准备两个空结点 pre用来保存先前结点、next用来做临时变量
  • 在头结点node遍历的时候此时为1结点
    • next = 1结点.next(2结点)
    • 1结点.next=pre(null)
    • pre = 1结点
    • node = 2结点
  • 进行下一次循环node=2结点
    • next = 2结点.next(3结点)
    • 2结点.next=pre(1结点)=>即完成2->1
    • pre = 2结点
    • node = 3结点
  • 进行循环…

迭代的过程：

  1. Initialize three pointers prev as NULL, curr as head and next as NULL.

  2. Iterate trough the linked list. In loop, do following.
    // Before changing next of current,
    // store next node
    next = curr->next

    // Now change next of current
    // This is where actual reversing happens
    curr->next = prev

    // Move prev and curr one step forward
    prev = curr
    curr = next

递归的过程

1) Divide the list in two parts - first node and rest of the linked list.

2) Call reverse for the rest of the linked list.

3) Link rest to first.

4) Fix head pointer

代码

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode prev = null; // 前一个节点从null开始
        ListNode curr = head; // 当前节点从第一个节点开始
        
        while (curr != null) {
            ListNode temp = curr.next; // 第一步，临时变量记住当前节点的下一个
            curr.next = prev; // 第二步，将当前节点的下一个指向前一个
            prev = curr; //第三步，将前一个指针向后移动一步
            curr = temp; // 第四步，将当前指针往后移动一步
        }
        
        return prev; // 最后返回prev在最后一个节点处，此时curr在最后一个节点后面的null处
    }
}

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
	public ListNode reverseList(ListNode head) {
		if (head == null || head.next == null) {
			return head;
		}
		ListNode result = reverseList(head.next);//逐步递归到最后两个结点
				
		//现在开始翻转两个结点，并“归”回去
		head.next.next = head;
		head.next = null;

		return result;
	}
}
This site is open source. Improve this page.