검지offer---반전 체인 시계

제목: 체인 테이블을 입력하여 체인 테이블을 반전시킨 후 체인 테이블의 모든 요소를 출력합니다.

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/

방법

public class Solution {
    ListNode node = null;
    public ListNode ReverseList(ListNode head) {
        if(head == null ||head.next == null){
            return head;
        }
        node = ReverseList(head.next);
    head.next.next = head;
        head.next = null;
        return node;
    }
}

일반적인 상황에서 반전의 문제는 귀속 코드를 이용하여 쓰는 것이 비교적 간결하지만 호출 창고가 너무 깊어서 넘치는 단점도 있고 귀속 함수 호출 전후의 코드 블록의 특징도 어느 정도 이해해야 한다.

함수 호출 후의 코드 블록은 일반적으로 귀속 창고에 따라 창고 밑에서 창고 꼭대기로 역방향으로 실행된다

함수 호출 전의 코드는 창고 꼭대기에서 창고 밑바닥까지 실행됩니다..

따라서 귀속을 판단하는 종료 조건은 귀속 함수의 호출 전에 진행해야 한다

역방향 코드는 귀속 함수 호출 후에 진행됩니다

이 문제는 결국 반전 후의 두결점으로 돌아가야 하기 때문에

리턴의 값이 마지막 노드로 끊임없이 위로 떠다니는 것을 확정할 수 있다

그리고 노드 간의 관계 반전이 시작될 때 k번째 노드의next는 k+1을 가리키고 그를 k+1의next지향k로 반전시켜야 한다.이 반전 과정은 뒤에서 앞으로 진행해야 한다.앞뒤로 진행하면 1->2가 되고 2->1과 3 노드가 끊어진다.반대면 4->5->6 반전하면 4->5

방법 2

public class Solution {
    ListNode node;
    public ListNode ReverseList(ListNode head) {
        ListNode first = null;
        ListNode second = null;
        while(head != null){
            first = head.next;
            head.next = second;
            second = head;
            head = first;
        }
        return second;
    }
}

위에서 언급한 바와 같이 정방향으로 반전하면 체인 시계가 끊어지는 상황이 발생하고 다음 노드를 찾을 수 없다. 그러면 우리는 바늘을 사용하여 다음 노드를 계속 가리키고 이 바늘의next를 이전 노드를 가리키면 된다.