[LeetCode] 206. Reverse Linked List

1888 단어

1. 원제 링크:https://leetcode.com/problems/reverse-linked-list/


2. 문제풀이 사고방식

  • 주의: 일반적인 상황에서 반전 조작은 두 개의 지침이 있어야 한다
  • 창고 작업과 유사한 입고와 출고를 귀속시키는데 관건은 어떤 데이터를 입고하는가에 있다
  • 이 문제에 대해 반전 조작이기 때문에 창고에 들어가는 두 개의 바늘이 필요합니다.prev와cur 두 개의 바늘로 가정합니다
  • 반전할 수 있도록prev바늘은cur의next바늘이어야 한다. 이렇게 순서대로 창고를 나갈 때prev바늘이야말로 반전 체인표 과정의prev노드를 가리킨다

  • 교체 사고방식
  • 두 개의 바늘의 플러그법으로 체인 시계를 반전시킨다


    • 3. 알고리즘


    3.1 귀속 알고리즘
  • 우선, 귀속 함수의 기능을 확정해야 한다. 이곳의 귀속 함수 기능은 원 체인표를 되돌려 반전시킨 후의 헤드 노드이다
  • 귀속 종료 조건: 원 체인 테이블이 비어 있거나 원 체인 테이블은 하나의 노드만 있습니다

    • 3.2 교체 알고리즘
  • 새 체인 테이블의 머리에 노드를 삽입하는 데 사용할 벙어리 노드를 만듭니다
  • prev와cur 두 개의 바늘로 반전 조작을 한다

    • 4. 실현

    struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
     
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL || head->next == NULL) return head;
        
        ListNode *new_prev = head->next; // 
        ListNode *new_head = reverseList(head->next); // 
        new_prev->next = head;
        head->next = NULL;
        return new_head;
    }
};
     
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL) return head;
        ListNode dummy(-1);
        dummy.next = head;
        ListNode *head2 = &dummy;
        
        ListNode *prev = head2->next;
        ListNode *cur = prev->next;
        while(cur != NULL){
            prev->next = cur->next;
            cur->next = head2->next;
            head2->next = cur; // 
            cur = prev->next;
        }
        return dummy.next;
    }
};
    C 언어는 귀속적인 방법으로 함수 n을 작성합니다!
    1.5 두 갈래 나무(4)

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage