leetcode 25. k 개 반전 링크

1671 단어
제목 설명
하나의 체인 시 계 를 제시 하고 k 개의 노드 마다 한 조 를 뒤 집 으 며 뒤 집 힌 링크 를 되 돌려 줍 니 다.
k 는 정수 로 링크 의 길이 보다 작 거나 같 습 니 다.만약 에 노드 총수 가 k 의 정수 배가 아니라면 마지막 남 은 노드 를 원래 의 순서 로 유지 합 니 다.
예시:
      :1->2->3->4->5

  k = 2  ,    : 2->1->4->3->5

  k = 3  ,    : 3->2->1->4->5

설명:
  • 당신 의 알고리즘 은 상수 의 추가 공간 만 사용 할 수 있 습 니 다.
  • 노드 내부 의 값 을 단순히 바 꾸 는 것 이 아니 라 실제 적 으로 노드 교환 을 해 야 한다.

  • 문제 풀이 의 사고 방향.
    1.      K   ,   K   ,        ,  K   ,      ,return
    2.     K    ,    ,       
    

    코드 구현
    // ListNode Definition for singly-linked list.
    type ListNode struct {
        Val  int
        Next *ListNode
    }
    
    func reverseKGroup(head *ListNode, k int) *ListNode {
        if k < 2 || head == nil || head.Next == nil {
            return head
        }
    
        tail, needReverse := getTail(head, k)
    
        if needReverse {
            tailNext := tail.Next
            //   tail     
            tail.Next = nil
            head, tail = reverse(head, tail)
    
            //tail            
            tail.Next = reverseKGroup(tailNext, k)
        }
    
        return head
    }
    
    func getTail(head *ListNode, k int) (*ListNode, bool) {
        for k > 1 && head != nil {
            head = head.Next
            k--
        }
        return head, k == 1 && head != nil
    }
    
    func reverse(head, tail *ListNode) (*ListNode, *ListNode) {
        //    
        prev, cur := head, head.Next
        for cur != nil {
            prev, cur, cur.Next = cur, cur.Next, prev
        }
        return tail, head
    }
    

    GitHub
  • 소스 코드 전송 문
  • 프로젝트 에서 각종 데이터 구조 와 알고리즘 을 제공 하 는 Golang 실현, LeetCode 문제 풀이 방향 과 답
  • 제목 출처
    leetcode 25. k 개 반전 링크

    좋은 웹페이지 즐겨찾기