阅读:0       作者:严长生

链表反转方法详解(含实现代码)

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

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

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

下面就是通过反转指针来实现反转链表的代码。
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());
        }
    }
}
这样可以轻松地完成链表反转。