反转单链表

剑指offer系列面试题

题目：定义个函数，输入一个链表头节点，反转该连标点并输出翻转后链表的头结点

分析：

可以这样想，反转单链表，也即以前是a–>b,现在成了b–>a,所以必须有两个引用指向这两个节点（一个引用指向当前节点，一个引用指向当前节点的前一个节点），但是光有这两个引用是不行的，因为肯定要向前迭代，所以必须还有一个引用指向当前所指节点的下一个节点。这样才不至于使链表断裂。

之后要注意如果链表有头节点，还必须考虑头节点的问题。

代码：

package com.study;

import java.util.Scanner;

class ListNode {
    public int data;
    public ListNode next;

    public ListNode() {

    }
}

public class List {
    public static void CreateList(ListNode Node, int value) {
        if (Node == null)
            return;
        if (value != -1) {
            ListNode newNode = new ListNode();
            newNode.data = value;
            newNode.next = Node.next;
            Node.next = newNode;
        }
    }

    public static ListNode ReverseList(ListNode node) {
        if (node == null || node.next == null || node.next.next == null) // 链表中只有一个节点，没有反转的必要
            return null;
        ListNode p = node;
        ListNode q = p.next;
        ListNode r = q.next;
        p = null; // 先让头节点变为NULL
        while (q != null) {
            q.next = p;
            p = q;
            q = r;
            if (q != null)
                r = q.next;
        }
        ListNode head = new ListNode();
        head.next = p;
        return head;
    }

    public static void PrintList(ListNode head) {
        if (head == null)
            return;
        if (head.next != null) {
            head = head.next;
            while (head != null) {
                System.out.print(head.data + "-->");
                if (head.next != null)
                    head = head.next;
                else
                    break;
            }
            System.out.print("NULL");
        }
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        ListNode head = new ListNode();
        while (input.hasNext()) {
            int num = input.nextInt();
            if (num == -1)
                break;
            CreateList(head, num);
        }
        input.close();
        PrintList(head);
        System.out.println();
        ListNode rhead = ReverseList(head);
        PrintList(rhead);
    }
}

注意

考虑特殊情况，如链表只有一个节点。