反转链表

[PisecesPeng]

反转链表

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶 :
你可以迭代或递归地反转链表.你能否用两种方法解决这道题?

题目地址: https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/

[PisecesPeng]

解题思路

• 遍历链表直到尾端, 然后再从尾端开始向前构造链表

代码

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}

public static ListNode func(ListNode head) {
    if (head == null) return null;

    ListNode point = new ListNode(0);
    reverse(head, point);
    return point.next;
}

public static ListNode reverse(ListNode listNode, ListNode point) {
    ListNode val = new ListNode(listNode.val);
    ListNode tmp;
    // 一旦递归到链表末尾, 就开始回溯构造链表
    if (listNode.next != null)
        tmp = reverse(listNode.next, point);
    else
        tmp = point;
    tmp.next = val;
    return tmp.next;
}

[PisecesPeng]

LeetCode题解

解题思路

• 递归, 遍历到尾端再从尾到头构造链表

代码

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}

public ListNode func(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode newHead = func(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

[PisecesPeng]

LeetCode题解

解题思路

• 迭代, 在遍历的同时构造前后结点的关系

代码

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}

public ListNode func(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}