C/C++教程

NC23 划分链表

本文主要是介绍NC23 划分链表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

描述

给出一个长度为 n 的单链表和一个值 x ,单链表的每一个值为 listi ,请返回一个链表的头结点,要求新链表中小于 x 的节点全部在大于等于 x 的节点左侧,并且两个部分之内的节点之间与原来的链表要保持相对顺序不变。

题目解法:先找到链表的尾节点和链表的长度,判断节点数值是否大于给定值,是就插入到尾处。

可以使用虚拟的头结点对翻转过程进行简化,链表问题要考虑,极端值情况

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param x int整型 
     * @return ListNode类
     */
    public ListNode partition (ListNode head, int x) {
        // write code here
        if(head==null) return null;
        ListNode tail=null;
        ListNode temp=head;
        int len=1;
        while(temp.next!=null)
        {
            temp=temp.next;
            len++;
        }
        tail=temp;
        if(head==temp) return head;
        
        temp=new ListNode(Integer.MIN_VALUE);
        temp.next=head;
        ListNode head_temp=temp;
        ListNode temp_pre=temp;
        for(int i=0;i<=len;i++)
        {
            if(temp.val>=x)
            {
                temp_pre.next=temp.next;
                tail.next=temp;
                tail=temp;
                temp=temp.next;
                tail.next=null;
                continue;
            }
            temp_pre=temp;
            temp=temp.next;
            
        }
        return head_temp.next;
    }
}

这篇关于NC23 划分链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!