leetcode_206(체인 테이블 반전)

1. 문제의 대의가 하나의 단일 체인표를 반전시켜 귀속과 비귀속의 두 가지 형식을 실현한다
2. 체인 테이블 노드
public class ListNode {
    int val;
    ListNode next;
    public ListNode(int val) {
        this.val = val;
    }
}

3, 분석 1, 비귀속 해결 방안: 가장 쉽게 떠오르는 것은 세 가지 지침, p1, p2, p3, 체인 테이블 사항의 반전을 반복하는 것이다.(여기에서 주의해야 할 것은 p1, p2, p3의 초기화, 서로 다른 초기화는 체인 헤더의 다른 처리를 고려해야 한다는 것이다. 일반적인 초기는 p1이 비어 있다. 다음에 토론하자)
2, 반복 솔루션: 후면 노드를 고려할 때마다 반전됨
3, 삽입 반전: 두 번째부터 뒤에 있는 노드를 헤드 노드 뒤에 놓고 마지막으로 첫 번째 노드를 마지막에 놓는다.
4. 경계 처리
if (head == null || head.next == null) {
            return head;
        }

다섯, 코드 1, 세 개의 바늘
public static ListNode reverseList1(ListNode head) {
        if(head == null || head.next == null) {
    // 
            return head;
        }
        ListNode p1 = null;// 
        ListNode p2 = head;
        ListNode p3 = head.next;
        while(p3 != null) {
    // 
            p2.next = p1;
            p1 = p2;
            p2 = p3;
            p3 = p3.next;
        }
        p2.next = p1;
        head = p2;
        return head;
    }

2, 귀속:
public static ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode p = head.next;
        ListNode n = reverseList2(p);// 
        head.next = null;
        p.next = head;
        return n;
    }

3, 삽입법
public static ListNode reverseList3(ListNode head) {
        if (head == null || head.next == null) {
    // 
            return head;
        }
        ListNode p = head.next;
        ListNode q = null;
        while(p.next != null) {
    // , head 
            q = p.next;// 
            p.next = q.next;
            q.next = head.next;// head 
            head.next = q;
        }
        p.next = head;// 
        head = p.next.next;// 
        p.next.next = null;// 
        return head;
    }

좋은 웹페이지 즐겨찾기