[LeetCode] - Reverse Linked List

Single LinkedList 순서를 역순으로

 

/*
        일단 순회부터
        while(head.next != null) {
            System.out.println(head.val);
            head = head.next; 1 = 2, 2 = 3, 3 = 4, 4 = 5, 5.next = null
        }
        */
        // return head;
        /*
        
	public class Main {
	public static void main(String[] args) {
		
		ListNode head = new ListNode(5,null);
		head = new ListNode(4,head);
		head = new ListNode(3,head);
		head = new ListNode(2,head);
		head = new ListNode(1,head);
		
		ListNode temp = new ListNode();
		head.next = temp;
		
		while(head.next != null) {
			System.out.println(head.val);
			head = head.next;
		}
		/* 
			null인 5의 직전 즉 4를 5가 가르키게 하고
			4 -> 3
			3 -> 2
			2 -> 1
			1... null
		*/
		head.next = head;
		System.out.println(head.val);
	}
}


        
        자 역순 어떻게 하지?
        1->2->3->4->5
        head.val = 1
        head.next = 2.pointer
        일단 마지막가서 next의 방향을 전으로 바꾸는게 필요할 거 같다
        전의 head를 가리키게 만드는 것...
        head = head.next;
        head.next = head?
        2가 1을 가리키게 해보자
        head.next = head
        1 = 1 X
        
        ListNode temp = new ListNode();
        
        while(head.next != null) {
            temp = head; -> null <- 1
            head = head.next; => 1 <- 2
            temp = head; -> 
            System.out.println(head.val); 2
        }
        System.out.println(head.val);
        return head;
        */

강의보고 따라하기

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode current = head;
        ListNode prev = null;
        
        while(current != null) {
            ListNode nextTemp = current.next;
            current.next = prev;
            prev = current;
            current = nextTemp;
        }
        return prev;
    }
}

Solution

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}