当前位置:首页>>LintCode-链表

LintCode-链表

  • 2022-07-15 23:16:40

35、翻转链表

LintCode-链表

解法一:递归

代码见下:

/**
 * Definition for ListNode
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param head: n
     * @return: The new head of reversed linked list.
     */
    public ListNode reverse(ListNode head) {
        // write your code here
        if(head==null){
            return null;
        }
        if(head.next==null){
            return head;
        }
        ListNode node = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return node;
    }
}
解法二:三个指针

定义3个指针,分别指向当前遍历到的结点(current)、它的前一个结点(prev)及后一个结点(nextNode)。
在遍历过程中,首先存储当前节点的后一个节点(nextNode = current.next),然后将当前节点的next指向前一个节点(prev),其次前一个节点再指向当前节点,最后再将当前节点指向最初记录的后一个节点,如此反复,直到当前节点的后一个节点为NULL时,则代表当前节点时反转后的头结点了。

整个过程只需遍历一次链表,效率较高,这是需要一些外部空间,实现代码如下:

package LinkedList;

/**
 * @ClassName Reverse2
 * Description TODO
 * @Auther 青青子衿
 * @Date 2019/5/7 13:53
 */
public class Reverse2 {
    private static class ListNode{
        private ListNode next;
        private Object value;

        public ListNode(Object value) {
            super();
            this.value = value;
        }
    }

    public static ListNode reverseLinkedList(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        ListNode reverseHead = null;
        ListNode current = head;
        ListNode prev = null;
        while (current != null) {
            ListNode nextNode = current.next;
            if (nextNode == null) {
                reverseHead = current;
            }
            current.next = prev;
            prev = current;
            current = nextNode;
        }
        return reverseHead;
    }

    public static void main(String[] args){
        int[] arr={1,2,3,4,5,6,7,8,9};
        ListNode head = new ListNode(arr[0]);
        ListNode p = head;
        for (int i = 1; i < arr.length; i++) {
            p.next = new ListNode(arr[i]);
            p = p.next;
        }
        p = head;
        while (p != null) {
            System.out.print(p.value + " ");
            p = p.next;
        }
        System.out.println();
        head = reverseLinkedList(head);
        while (head != null) {
            System.out.print(head.value + " ");
            head = head.next;
        }
    }
}

运行结果:

1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1

36、翻转链表II

LintCode-链表

猜你喜欢