Category List with custom urls

get_categories() is handy function to get list of categories with all information such as id & name of each category etc.

This code might work. The $category->term_id will return the unique id for each category and $category->name will return the name to display to user.

<?php 
$args=array(
  'orderby' => 'name',
  'order' => 'ASC'
  );
$categories=get_categories($args);
foreach($categories as $category) {
echo '<a href="https://wordpress.stackexchange.com/questions/59862/?search-type=normal&s=".$category->term_id."">'.$category->name.'</a>';
}
?>

Update –

Here is code which uses custom WordPress walker class to edit the links. Put this into your themes functions.php

 //usage  wp_list_categories( array('walker' => new wpse_59862_walker() ) ) 

class wpse_59862_walker extends Walker_Category {

    // copied function from /inlcude/category-template.php and edited as per requirements
    function start_el( &$output, $category, $depth = 0, $args = array(), $id = 0 ) {
        extract($args);

        $cat_name = esc_attr( $category->name );
        $cat_name = apply_filters( 'list_cats', $cat_name, $category );
        $my_blog_link = site_url("https://wordpress.stackexchange.com/"); //this is to return blog url

        //here I edited the link to meet your requirments.
        $link = '<a href="'.$my_blog_link."https://wordpress.stackexchange.com/questions/59862/?search-type=normal&s=".$category->term_id."" ';

        if ( $use_desc_for_title == 0 || empty($category->description) )
            $link .= 'title="' . esc_attr( sprintf(__( 'View all posts filed under %s' ), $cat_name) ) . '"';
        else
            $link .= 'title="' . esc_attr( strip_tags( apply_filters( 'category_description', $category->description, $category ) ) ) . '"';
        $link .= '>';
        $link .= $cat_name . '</a>';

        if ( !empty($feed_image) || !empty($feed) ) {
            $link .= ' ';

            if ( empty($feed_image) )
                $link .= '(';

            $link .= '<a href="' . esc_url( get_term_feed_link( $category->term_id, $category->taxonomy, $feed_type ) ) . '"';

            if ( empty($feed) ) {
                $alt=" alt="" . sprintf(__( 'Feed for all posts filed under %s' ), $cat_name ) . '"';
            } else {
                $title=" title="" . $feed . '"';
                $alt=" alt="" . $feed . '"';
                $name = $feed;
                $link .= $title;
            }

            $link .= '>';

            if ( empty($feed_image) )
                $link .= $name;
            else
                $link .= "<img src="$feed_image"$alt$title" . ' />';

            $link .= '</a>';

            if ( empty($feed_image) )
                $link .= ')';
        }

        if ( !empty($show_count) )
            $link .= ' (' . intval($category->count) . ')';

        if ( 'list' == $args['style'] ) {
            $output .= "\t<li";
            $class="cat-item cat-item-" . $category->term_id;
            if ( !empty($current_category) ) {
                $_current_category = get_term( $current_category, $category->taxonomy );
                if ( $category->term_id == $current_category )
                    $class .=  ' current-cat';
                elseif ( $category->term_id == $_current_category->parent )
                    $class .=  ' current-cat-parent';
            }
            $output .=  ' class="' . $class . '"';
            $output .= ">$link\n";
        } else {
            $output .= "\t$link<br />\n";
        }
    }

}