链表反转

剑指 Offer 06. 从尾到头打印链表

上面这道题本身不难,利用栈就可以了。

但是上次小米面试的时候,面试官让我反转一个链表,觉得比这道Offer 06 稍微难一丢丢。赋值顺序、返回的新头节点还是需要思考一下的。

直接用的Offer 06 的数据结构。

【不得不感叹,博客园的代码插入是真难用,复制粘贴格式都要变】

 

class Solution {
    public static void main(String[] args) {
        Solution o = new Solution();
        int[] arr = {1,2,3,4};
        ListNode head1 = o.create(arr);
        System.out.println("链表:");
        o.print(head1);
        System.out.println();

        ListNode head2 = o.reverse(head1);
        System.out.println("链表反转后:");
        o.print(head2);
    }
    
    //链表反转
    public ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        ListNode next = head;
        while(next != null){
            next = curr.next; //这个必须放前面,如果放后面,curr.next就已经被更改为prev了,就丢掉了。

            curr.next = prev;
            
            prev = curr;
            curr = next;
        }

        //最后一个curr是null,prev才是组后一个元素的地址,也就是新链表的头结点。
        return prev;
    }
  
  //根据数组创建链表 
    public ListNode create(int[] arr){
        ListNode head = new ListNode(arr[0]);
        ListNode curr = head;
        for(int i = 1;i<arr.length;i++){
            ListNode tmp = new ListNode(arr[i]);
            curr.next = tmp;
            tmp.next = null;
            curr = tmp;
        }
        return head;
    }
  
  //给定链表头节点,遍历输出链表
    public void print(ListNode head){
        ListNode curr = head;
        while(curr != null){
            System.out.print(curr.val+" ");
            curr = curr.next;
        }
    }
}

//链表定义
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

 

链表反转

上一篇:Legacy CodeForces - 787D


下一篇:jmeter从csv文件中取数据设置变量的方法