作者：解学武

怎么反转链表呢？这个是面试中经常出现的一道题。一般在数据结构或者算法的面试题中，尽量不使用额外的空间去实现，尽管现在的计算机空间很充足，但是面试考察的还是对于整体性能的考虑。

方法其实有很多，我们可以依次遍历链表，然后依次使用头插入的方法来达到目的。

其中有个简单的方法，就是把链表的每个指针反转。

下面就是通过反转指针来实现反转链表的代码。

public void reverse(){
    Node temp = first;
    last = temp;
    Node next = first.getNext();
    for(int i =0; i<size- 1;i++){
        Node nextNext = next.getNext();
        next.setNext(temp);
        temp = next;
        next = nextNext;
    }
    last.setNext(null);
    first = temp;
}

这部分代码应该在 Link 类里，通过反转指针实现链表反转。

接下来我们看看测试代码。

package me.irfen.algorithm.ch02.extend;
import me.irfen.algorithm.ch02.Link;
public class LinkReverseTest {
    public static void main(String[] args) {
        Link link = new Link();
        link.addLast(1);
        link.addLast(2);
        link.addLast(3);
        link.addLast(4);
        printAllElements(link);
        link.reverse();
        printAllElements(link);
    }
    private static void printAllElements(Link link) {
        for (int i = 0; i < link.size(); i++) {
            System.out.println(link.get(i).getData());
        }
    }
}

这样可以轻松地完成链表反转。
声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。