C++LeetCode 구현(19.링크 마지막 N 번 째 노드 제거)

[LeetCode]19.Nth Node From End of List 를 제거 하고 링크 의 마지막 N 번 째 노드 를 제거 합 니 다.
Given a linked list, remove the nth node from the end of list and return its head.
For example,

Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.
이 문 제 는 링크 의 마지막 N 번 째 노드 를 제거 하고 n 을 제한 하 는 것 이 반드시 효과 적 입 니 다.즉,n 은 링크 의 요소 총수 보다 크 지 않 습 니 다.그리고 문 제 를 한 번 에 옮 겨 다 니 며 해결 해 야 한다 면 비교적 교묘 한 방법 을 생각해 야 한다.예 를 들 어 먼저 고려 해 야 할 때 꼴찌 N 번 째 노드 를 어떻게 찾 는 지,한 번 만 옮 겨 다 닐 수 있 기 때문에 링크 에 있 는 요소 의 개 수 를 한 번 에 통계 할 수 없고 해당 하 는 위치 에 옮 겨 다 니 면 제거 해 야 한다.그러면 두 개의 지침 으로 문제 풀이,pre 와 cur 지침 을 도와 야 한다.먼저 cur 포인터 가 N 보 앞으로 갑 니 다.이때 cur 가 비어 있 으 면 N 이 링크 의 길 이 를 설명 합 니 다.제거 해 야 할 요소 입 니 다.그러면 이때 head->next 로 돌아 가면 됩 니 다.cur 가 존재 하면 계속 내 려 갑 니 다.이때 pre 포인터 도 따라 갑 니 다.cur 가 마지막 요소 일 때 까지 멈 춥 니 다.이때 pre 는 요소 의 이전 요 소 를 제거 하 는 것 을 가리 키 고 있 습 니 다.포인터 가 제거 해 야 할 요 소 를 건 너 뛰 면 됩 니 다.코드 는 다음 과 같 습 니 다.
방식 1:

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if (!head->next) return NULL;
        ListNode *pre = head, *cur = head;
        for (int i = 0; i < n; ++i) cur = cur->next;
        if (!cur) return head->next;
        while (cur->next) {
            cur = cur->next;
            pre = pre->next;
        }
        pre->next = pre->next->next;
        return head;
    }
};
방식 2:

class Solution {
public:
    int getLength(ListNode* head) {
        int length = 0;
        while (head) {
            ++length;
            head = head->next;
        }
        return length;
    }

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode* cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur->next;
        }
        cur->next = cur->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};
여기 서 C++구현 LeetCode(19.링크 꼴찌 N 번 째 노드 제거)에 관 한 글 을 소개 합 니 다.더 많은 관련 C++구현 링크 꼴찌 N 번 째 노드 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 보 세 요.앞으로 많은 응원 바 랍 니 다!

좋은 웹페이지 즐겨찾기